perm filename PHIL.ART[ESS,JMC] blob
sn#005493 filedate 1971-09-12 generic text, type T, neo UTF8
00100 SOME PHILOSOPHICAL PROBLEMS FROM THE STANDPOINT OF
00200 ARTIFICIAL INTELLIGENCE
00300
00400
00500 by
00600
00700 John McCarthy, Stanford University
00800 Patrick Hayes, University of Edinburgh
00900
01000
01100 Abstract
01200
01300
01400 A computer program capable of acting intelligently in the world must
01500 have a general representation of the world in terms of which its
01600 inputs are interpreted. Designing such a program requires
01700 commitments about what knowledge is and how it is obtained. Thus,
01800 some of the major traditional problems of philosophy arise in
01900 artificial intelligence.
02000 More specifically, we want a computer program that decides what
02100 to do by inferring in a formal language that a certain strategy will
02200 achieve its assigned goal. This requires formalizing concepts of
02300 causality, ability, and knowledge. Such formalisms are also
02400 considered in philosophical logic. The first part of the paper
02500 begins with a philosophical point of view that seems to arise
02600 naturally once we take seriously the idea of actually making an
02700 intelligent machine. We go on to the notions of metaphysically and
02800 epistemologically adequate representations of the world and then to
02900 an explanation of "can", "causes", and "knows" in terms of a
03000 representation of the world by a system of interacting automata. A
03100 proposed resolution of the problem of free will in a deterministic
03200 universe and of counterfactual conditional sentences is presented.
03300 The second part is mainly concerned with formalisms within
03400 which it can be proved that a strategy will achieve a goal. Concepts
03500 of situation, fluent, future operator, action, strategy, result of a
03600 strategy and knowledge are formalized. A method is given of
03700 constructing a sentence of first order logic which will be true in
03800 all models of certain axioms if and only if a certain strategy will
03900 achieve a certain goal.
04000 The formalism of this paper represents an advance over
04100 McCarthy (1963) and Green (1968) in that it permits proof of the
04200 correctness of strategies that contain loops and strategies that
04300 involve the acquisition of knowledge, and it is also somewhat more
04400 concise.
04500 The third part discusses open problems in extending the
04600 formalism of Part II.
04700 The fourth part is a review of work in philosophical logic in
04800 relation to problems of artificial intelligence and a discussion of
04900 previous efforts to program "general intelligence" from the point of
05000 view of this paper.
00050 %B,1
00100 1. PHILOSOPHICAL QUESTIONS
00200
00300
00400 Why Artificial Intelligence Needs Philosophy
00500
00600 The idea of an intelligent machine is old, but serious work on the
00700 artificial intelligence problem or even serious understanding of what
00800 the problem is awaited the stored program computer. We may regard
00900 the subject of artificial intelligence as beginning with Turing's
01000 article "Computing Machinery and Intelligence" (Turing 1950) and with
01100 Shannon`s (1950) discussion of how a machine might be programmed to
01200 play chess.
01300 Since that time, progress in artificial intelligence has been
01400 mainly along the following lines. Programs have been written to solve
01500 a class of problems that give humans intellectual difficulty:
01600 examples are playing chess or checkers, proving mathematical
01700 theorems, transforming one symbolic expression into another by given
01800 rules, integrating expressions composed of elementary functions,
01900 determining chemical compounds consistent with mass-spectrographic
02000 and other data. In the course of designing these programs
02100 intellectual mechanisms of greater or lesser generality are
02200 identified sometimes by introspection, sometimes by mathematical
02300 analysis, and sometimes by experiments with human subjects. Testing
02400 the programs sometimes leads to better understanding of the
02500 intellectual mechanisms and the identification of new ones.
02600 An alternative approach is to start with the intellectual
02700 mechanisms (for example, memory, decision-making by comparisons of
02800 scores made up of weighted sums of sub-criteria, learning,
02900 tree-search, extrapolation) and make up problems that exercise these
03000 mechanisms.
03100 In our opinion the best of this work has led to increased
03200 understanding of intellectual mechanisms and this is essential for
03300 the development of artificial intelligence even though few
03400 investigators have tried to place their particular mechanism in the
03500 general context of artificial intelligence. Sometimes this is
03600 because the investigator identifies his particular problem with the
03700 field as a whole; he thinks he sees the woods when in fact he is
03800 looking at a tree. An old but not yet superseded discussion on
03900 intellectual mechanisms is in Minsky (1961); see also Newell's (1965)
04000 review of the state of artificial intelligence.
04100 There have been several attempts to design intelligence with
04200 the same kind of flexibility as that of a human. This has meant
04300 different things to different investigators, but none has met with
04400 much success even in the sense of general intelligence used by the
04500 investigator in question. Since our criticism of this work will be
04600 that it does not face the philosophical problems discussed in this
04700 paper we shall postpone discussing it until a concluding section.
04800 However, we are obliged at this point to present our notion of
04900 general intelligence.
00100 It is not difficult to give sufficient conditions for general
00200 intelligence. Turing's idea that the machine should successfully
00300 pretend to a sophisticated observer to be a human being for half an
00400 hour will do. However, if we direct our efforts towards such a goal
00500 our attention is distracted by certain superficial aspects of human
00600 behaviour that have to be imitated. Turing excluded some of these by
00700 specifying that the human to be imitated is at the end of a teletype
00800 line, so that voice, appearance, smell, etc., do not have to be
00900 considered. Turing did allow himself to be distracted into
01000 discussing the imitation of human fallibility in arithmetic,
01100 laziness, and the ability to use the English language.
01200 However, work on artificial intelligence, especially general
01300 intelligence, will be improved by a clearer idea of what intelligence
01400 is. One way is to give a purely behavioural or black-box definition.
01500 In this case we have to say that a machine is intelligent if it
01600 solves certain classes of problems requiring intelligence in humans,
01700 or survives in an intellectually demanding environment. This
01800 definition seems vague; perhaps it can be made somewhat more precise
01900 without departing from behavioural terms, but we shall not try to do
02000 so.
02100 Instead, we shall use in our definition certain structures
02200 apparent to introspection, such as knowledge of facts. The risk is
02300 twofold: in the first place we might be mistaken in our introspective
02400 views of our own mental structure; we may only think we use facts.
02500 In the second place there might be entities which satisfy
02600 behaviourist criteria of intelligence but are not organized in this
02700 way. However, we regard the construction of intelligent machines as
02800 fact manipulators as being the best bet both for constructing
02900 artificial intelligence and understanding natural intelligence.
03000 We shall, therefore, be interested in an intelligent entity
03100 that is equipped with a representation or model of the world. On the
03200 basis of this representation a certain class of internally posed
03300 questions can be answered, not always correctly. Such questions are
03400
03500 1. What will happen next in a certain aspect of
03600 the situation?
03700 2. What will happen if I do a certain action?
03800 3. What is 3 + 3?
03900 4. What does he want?
04000 5. Can I figure out how to do this or must
04100 I get information from someone else or something
04200 else?
04300
04400 The above are not a fully representative set of questions and we do
04500 not have such a set yet.
04600 On this basis we shall say that an entity is intelligent if
04700 it has an adequate model of the world (including the intellectual
04800 world of mathematics, understanding of its own goals and other mental
04900 proceesses), if it is clever enough to answer a wide variety of
05000 questions on the basis of this model, if it can get additional
05100 information from the external world when required, and can perform
00100 such tasks in the external world as its goals demand and its physical
00200 abilities permit.
00300 According to this definition intelligence has two parts,
00400 which we shall call the epistemological and the heuristic. The
00500 epistemological part is the representation of the world in such a
00600 form that the solution of problems follows from the facts expressed
00700 in the representation. The heuristic part is the mechanism that on
00800 the basis of the information solves the problem and decides what to
00900 do. Most of the work in artificial intelligence so far can be
01000 regarded as devoted to the heuristic part of the problem. This
01100 paper, however, is entirely devoted to the epistemological part.
01200 Given this notion of intelligence the following kinds of
01300 problems arise in constructing the epistemological part of an
01400 artificial intelligence:
01500 1. What kind of general representation of the world will
01600 allow the incorporation of specific observations and new
01700 scientific laws as they are discovered?
01800 2. Besides the representation of the physical world what
01900 other kind of entities have to be provided for? For
02000 example, mathematical systems, goals, states of
02100 knowledge.
02200 3. How are observations to be used to get knowledge about
02300 the world, and how are the other kinds of knowledge to be
02400 obtained? In particular what kinds of knowledge about the
02500 system's own state of mind are to be provided for?
02600 4. In what kind of internal notation is the system's
02700 knowledge to be expressed?
02800
02900 These questions are identical with or at least correspond to some
03000 traditional questions of philosophy, especially in metaphysics,
03100 epistemology and philosophic logic. Therefore, it is important for
03200 the research worker in artificial intelligence to consider what the
03300 philosophers have had to say.
03400 Since the philosophers have not really come to an agreement
03500 in 2500 years it might seem that artificial intelligence is in a
03600 rather hopeless state if it is to depend on getting concrete enough
03700 information out of philosophy to write computer programs.
03800 Fortunately, merely undertaking to embody the philosophy in a
03900 computer program involves making enough philosophical presuppositions
04000 to exclude most philosophy as irrelevant. Undertaking to construct a
04100 general intelligent computer program seems to entail the following
04200 presuppositions:
04300
04400 1. The physical world exists and already contains some
04500 intelligent machines called people.
04600 2. Information about this world is obtainable through the
04700 senses and is expressible internally.
04800 3. Our common-sense view of the world is approximately
04900 correct and so is our scientific view.
00100 4. The right way to think about the general problems of
00200 metaphysics and epistemology is not to attempt to clear
00300 one's own mind of all knowledge and start with 'Cogito
00400 ergo sum' and build up from there. Instead, we propose to
00500 use all of our knowledge to construct a computer program
00600 that knows. The correctness of our philosophical system
00700 will be tested by numerous comparisons between the
00800 beliefs of the program and our own observations and
00900 knowledge. (This point of view corresponds to the
01000 presently dominant attitude towards the foundations of
01100 mathematics. We study the structure of mathematical
01200 systems--from the outside as it were--using whatever
01300 metamathematical tools seem useful instead of assuming as
01400 little as possible and building up axiom by axiom and
01500 rule by rule within a system.)
01600 5. We must undertake to construct a rather comprehensive
01700 philosophical system, contrary to the present tendency to
01800 study problems separately and not try to put the results
01900 together.
02000 6. The criterion for definiteness of the system becomes much
02100 stronger. Unless, for example, a system of epistemology
02200 allows us, at least in principle, to construct a computer
02300 program to seek knowledge in accordance with it, it must
02400 be rejected as too vague.
02500 7. The problem of 'free will' assumes an acute but concrete
02600 form. Namely, in common-sense reasoning, a person often
02700 decides what to do by evaluating the results of the
02800 different actions he can do. An intelligent program must
02900 use this same process, but using an exact formal sense of
03000 "can", must be able to show that it has these
03100 alternatives without denying that it is a deterministic
03200 machine.
03300 8. The first task is to define even a naive, common-sense
03400 view of the world precisely enough to program a computer
03500 to act accordingly. This is a very difficult task in
03600 itself.
03700
03800 We must mention that there is one possible way of getting an
03900 artificial intelligence without having to understand it or solve the
04000 related philosophical problems. This is to make a computer
04100 simulation of natural selection in which intelligence evolves by
04200 mutating computer programs in a suitably demanding environment. This
04300 method has had no substantial success so far, perhaps due to
04400 inadequate models of the world and of the evolutionary process, but
04500 it might succeed. It would seem to be a dangerous procedure, for a
04600 program that was intelligent in a way its designer did not understand
04700 might get out of control. In any case, the approach of trying to
04800 make an artificial intelligence through understanding what
04900 intelligence is, is more congenial to the present authors and seems
05000 likely to succeed sooner.
00100 Reasoning programs and the Missouri program
00200
00300 The philosophical problems that have to be solved will be clearer in
00400 connection with a particular kind of proposed intelligent program,
00500 called a reasoning program or RP for short. RP interacts with the
00600 world through input and output devices some of which may be general
00700 sensory and motor organs (for example, television cameras,
00800 microphones, artificial arms) and others of which are communication
00900 devices (for example, teletypes or keyboard-display consoles).
01000 Internally, RP may represent information in a variety of ways. For
01100 example, pictures may be represented as dot arrays or a list of
01200 regions and edges with classifications and adjacency relations.
01300 Scenes may be represented as lists of bodies with positions, shapes,
01400 and rates of motion. Situations may be represented by symbolic
01500 expressions with allowed rules of transformation. Utterances may be
01600 represented by digitized functions of time, by sequences of phonemes,
01700 and parsings of sentences.
01800 However, one representation plays a dominant role and in
01900 simpler systems may be the only representation present. This is a
02000 representation by sets of sentences in a suitable formal logical
02100 language, for example omega order logic with function symbols,
02200 description operator, conditional expressions, sets, etc. Whether we
02300 must include modal operators with their referential opacity is
02400 undecided. This representation dominates in the following sense:
02500
02600 1. All other data structures have linguistic descriptions
02700 that give the relations between the structures and what
02800 they tell about the world.
02900 2. The subroutines have linguistic descriptions that tell
03000 what they do, either internally manipulating data, or
03100 externally manipulating the world.
03200 3. The rules that express RP's beliefs about how the world
03300 behaves and that give the consequences of strategies are
03400 expressed linguistically.
03500 4. RP's goals, as given by the experimenter, its derived
03600 subgoals, its opinion on its state of progress are all
03700 linguistically expressed.
03800 5. We shall say that RP's information is adequate to solve a
03900 problem if it is a logical consequence of all these
04000 sentences that a certain strategy of action will solve
04100 it.
04200 6. RP is a deduction program that tries to find strategies
04300 of action that it can prove will solve a problem; on
04400 finding one, it executes it.
04500 7. Strategies may involve subgoals which are to be solved by
04600 RP, and part or all of a strategy may be purely
04700 intellectual, that is, may involve the search for a
04800 strategy, a proof, or some other intellectual object that
04900 satisfies some criteria.
00100 Such a program was first discussed in McCarthy (1959) and was called
00200 the Advice Taker. In McCarthy (1963) a preliminary approach to the
00300 required formalism, now superseded by this paper, was presented. This
00400 paper is in part an answer to Y. Bar-Hillel's comment, when the
00500 original paper was presented at the 1958 Symposium on the
00600 Mechanization of Thought Processes, that the paper involved some
00700 philosophical presuppositions.
00800 Constructing RP involves both the epistemological and the
00900 heuristic parts of the artificial intelligence problem: that is, the
01000 information in memory must be adequate to determine a strategy for
01100 achieving the goal (this strategy may involve the acquisition of
01200 further information) and RP must be clever enough to find the
01300 strategy and the proof of its correctness. Of course, these problems
01400 interact, but since this paper is focused on the epistemological
01500 part, we mention the Missouri program (MP) that involves only this
01600 part.
01700 The Missouri program (its motto is, 'Show me') does not try
01800 to find strategies or proofs that the strategies achieve a goal.
01900 Instead, it allows the experimenter to present it proof steps and
02000 checks their correctness. Moreover, when it is 'convinced' that it
02100 ought to perform an action or execute a strategy it does so. We may
02200 regard this paper as being concerned with the construction of a
02300 Missouri program that can be persuaded to achieve goals.
02400
02500
02600 Representations of the world
02700
02800 The first step in the design of RP or MP is to decide what
02900 structure the world is to be regarded as having, and how information
03000 about the world and its laws of change are to be represented in the
03100 machine. This decision turns out to depend on whether one is talking
03200 about the expression of general laws or specific facts. Thus, our
03300 understanding of gas dynamics depends on the representation of a gas
03400 as a very large number of particles moving in space; this
03500 representation plays an essential role in deriving the mechanical,
03600 thermal electrical and optical properties of gases. The state of the
03700 gas at a given instant is regarded as determined by the position,
03800 velocity and excitation states of each particle. However, we never
03900 actually determine the position, velocity or excitation of even a
04000 single molecule. Our practical knowledge of a particular sample of
04100 gas is expressed by parameters like the pressure, temperature and
04200 velocity fields or even more grossly by average pressures and
04300 temperatures. From our philosophical point of view this is entirely
04400 normal, and we are not inclined to deny existence to entities we
04500 cannot see, or to be so anthropocentric as to imagine that the world
04600 must be so constructed that we have direct or even indirect access
04700 to all of it.
04800 From the artificial intelligence point of view we can then
04900 define three kinds of adequacy for representations of the world.
00100 A representation is called metaphysically adequate if the
00200 world could have that form without contradicting the facts of the
00300 aspect of reality that interests us. Examples of metaphysically
00400 adequate representations for different aspects of reality are:
00500 1. The representation of the world as a collection of
00600 particles interacting through forces between each pair of
00700 particles.
00800 2. Representation of the world as a giant quantum-mechanical
00900 wave function.
01000 3. Representation as a system of interacting discrete
01100 automata. We shall make use of this representation.
01200
01300 Metaphysically adequate representations are mainly useful for
01400 constructing general theories. Deriving observable consequences from
01500 the theory is a further step.
01600 A representation is called epistemologically adequate for a
01700 person or machine if it can be used practically to express the facts
01800 that one actually has about the aspect of the world. Thus none of
01900 the above-mentioned representations are adequate to express facts
02000 like 'John is at home' or 'dogs chase cats' or 'John's telephone
02100 number is 321-7580'. Ordinary language is obviously adequate to
02200 express the facts that people communicate to each other in ordinary
02300 language. It is not, for instance, adequate to express what people
02400 know about how to recognize a particular face. The second part of
02500 this paper is concerned with an epistemologically adequate formal
02600 representation of common-sense facts of causality, ability and
02700 knowledge.
02800 A representation is called heuristically adequate if the
02900 reasoning processes actually gone through in solving a problem are
03000 expressible in the language. We shall not treat this somewhat
03100 tentatively proposed concept further in this paper except to point
03200 out later that one particular representation seems epistemologically
03300 but not heuristically adequate.
03400 In the remaining sections of the first part of the paper we
03500 shall use the representations of the world as a system of interacting
03600 automata to explicate notions of causality, ability and knowledge
03700 (including self-knowledge).
00100 The automaton representation and the notion of `can`
00200
00300 Let "S" be a system of interacting discrete finite automata such as
00400 that shown in figure 1
00500 ----------
00600 | |
00700 | |
00800 | 1 |----------
00900 | | 5|
01000 | | |
01100 ---------- | |
01200 ↑ | | |
01300 2| | | |
01400 | | | |
01500 | |3 | |6
01600 | ↓ ↓ ↓
01700 ---------- ---------- ----------
01800 1| | 4| | 7| | 9
01900 -------→| |-----→| |-----→| |-----→
02000 | | | | | |
02100 | 2 | | 3 |8 | 4 |
02200 | | | |←------| |
02300 ---------- ---------- ----------
02400 ↑ |
02500 | |
02600 | 10 |
02700 ---------------------------------
02800 Figure 1
02900
03000 Each box represents a subautomaton and each line represents a
03100 signal. Time takes on integer values and the dynamic behaviour of
03200 the whole automaton is given by the equations:
03300 (1) a1(t+1)=A1(a1(t),s3(t))
03400 a2(t+1)=A2(a2(t),s1(t),s2(t),s0(t))
03500 a3(t+1)=A3(a3(t),s4(t),s5(t),s6(t))
03600 a4(t+1)=A4(a4(t),s7(t))
03700 (2) s2(t)=S2(a1(t))
03800 s3(t)=S3(a2(t))
03900 s4(t)=S4(a2(t))
04000 s5(t)=S5(a1(t))
04100 s7(t)=S7(a4(t))
04200 s8(t)=S8(a4(t))
04300 s9(t)=S9(a4(t))
04400 s0(t)=S0(a4(t))
04500 The interpretation of these equations is that the state of any
04600 automaton at time %t+1% is determined by its state at time "t" and by
04700 the signals received at time "t". The value of a paticular signal at
04800 time "t" is determined by the state at time "t" of the automaton from
04900 which it comes. Signals without a source automaton represent inputs
05000 from the outside and signals without a destination represent outputs.
00100 Finite automata are the simplest examples of systems that
00200 interact over time. They are completely deterministic; if we know
00300 the initial states of all the automata and if we know the inputs as a
00400 function of time, the behaviour of the system is completely detemined
00500 by equations (1) and (2) for all future time.
00600 The automaton representation consists in regarding the world
00700 as a system of interacting subautomata. For example, we might regard
00800 each person in the room as a subautomaton and the environment as
00900 consisting of one or more additional subautomata. As we shall see,
01000 this representation has many of the qualitative properties of
01100 interactions among things and persons. However, if we take the
01200 representation too seriously and attempt to represent particular
01300 situations by systems of interacting automata we encounter the
01400 following difficulties:
01500 1. The number of states required in the subautomata is very
01600 large, for example 2↑10↑10, if we try to represent
01700 someone`s knowledge. Automata this large have to be
01800 represented by computer programs, or in some other way
01900 that does not involve mentioning states individually.
02000 2. Geometric information is hard to represent. Consider,
02100 for example, the location of a multi-jointed object such
02200 as a person or a matter of even more difficulty - the
02300 shape of a lump of clay.
02400 3. The system of fixed interconnections is inadequate.
02500 Since a person may handle any object in the room, an
02600 adequate automaton representation would require signal
02700 lines connecting him with every object.
02800 4. The most serious objection, however, is that (in our
02900 terminology) the automaton representation is
03000 epistemologically inadequate. Namely, we do not ever
03100 know a person well enough to list his internal states.
03200 The kind of information we do have about him needs to be
03300 expressed in some other way.
03400
03500 Nevertheless, we may use the automaton representation for concepts of
03600 "can," "causes," some kinds of counterfactual statements (`If I had
03700 struck this match yesterday it would have lit`) and, with some
03800 elaboration of the representation, for a concept of "believes."
03900 Let us consider the notion of "`can.`" Let "S" be a system of
04000 subautomata without external inputs such as that of figure 2. Let
04100 "p" be one of the subautomata, and suppose that there are "m" signal
04200 lines coming out of "p". What "p" can do is defined in terms of a
04300 new system "S(p)", which is obtained from the system "S" by
04400 disconnecting the "m" signal lines coming from "p" and replacing them
04500 by "m" external input lines to the system. In figure 2, subautomaton
04600 1 has one output, and in the system "S1" this is replaced by an
04700 external input. The new system "S(p)" always has the same set of
04800 states as the system "S". Now let "π" be a condition on the state
04900 such as, `"a2" is even` or %"`a2=a3`"%. (In the applications "π" may
05000 be a condition like `The box is under the bananas`.)
00100 We shall write
00200 can(p,π,s)
00300 which is read, `The subautomaton "p" "can" bring about the condition
00400 "π" in the situation "s" if there is a sequence of outputs from the
00500 automaton "Sp" that will eventually put "S" into a state "a`" that
00600 satisfies "π(a`)". In other words, in determining what "p" can
00700 achieve, we consider the effects of sequences of its actions, quite
00800 apart from the conditions that determine what it actually will do.
00900 In figure 2, let us consider the initial state "a" to be one
01000 in which all subautomata are initially in state "0". Then the
01100 reader will easily verify the following propositions:
01200 1. Subautomaton 2 "will" never be in state 1.
01300 2. Subautomaton 1 "can" put subautomaton 2 in state 1.
01400 3. Subautomaton 3 "cannot" put subautomaton 2 in state 1.
01500 ---------- ---------- ----------
01600 | | 1| | 3 | |
01700 | |----→| |←----| |
01800 | | | | | |
01900 | 1 | | 2 | | 3 |
02000 | | 2 | | | |
02100 | |←----| | | |
02200 | | | | | |
02300 ---------- ---------- ----------
02400
02500 Figure 2. System S
02600
02700 a1(t+1)=a1(t)+s2(t)
02800 a2(t+1)=a2(t)+s1(t)+2s3(t)
02900 a3(t+1)=if a3(t)=0 then 0 else a3(t)+1
03000
03100 s1(t)=if a1(t)=0 then 2 else 1
03200 s2(t)=1
03300 s3(t)=if a3(t)=0 then 0 else 1
03400
03500
03600 |
03700 ---------- 1| ---------- 3 ----------
03800 | | |-→| |←----| |
03900 | | | | | |
04000 | | | | | |
04100 | 1 | | 2 | | 3 |
04200 | | 2 | | | |
04300 | |←-----| | | |
04400 | | | | | |
04500 ---------- ---------- ----------
04600
04700 System S1
00100 We claim that this notion of "can" is, to a first
00200 approximation, the appropriate one for an automaton to use internally
00300 in deciding what to do by reasoning. We also claim that it
00400 corresponds in many cases to the common sense notion of "can" used in
00500 everyday speech.
00600 In the first place, suppose we have an automaton that decides
00700 what to do by reasoning, for example suppose it is a computer using
00800 an RP. Then its output is determined by the decisions it makes in
00900 the reasoning process. It does not know (has not computed) in
01000 advance what it will do, and, therefore, it is appropriate that it
01100 considers that it can do anything that can be achieved by some
01200 sequence of its outputs. Common-sense reasoning seems to operate in
01300 the same way.
01400 The above rather simple notion of "can" requires some
01500 elaboration both to represent adequately the commonsense notion and
01600 for practical purposes in the reasoning program.
01700 First, suppose that the system of automata admits external
01800 inputs. There are two ways of defining "can" in this case. One way
01900 is to assert "can(p,π,s)" if "p" can achieve "π" regardless of what
02000 signals appear on the external inputs. Thus, instead of requiring
02100 the existence of a sequence of outputs of "p" that achieves the goal
02200 we shall require the existence of a strategy where the output at any
02300 time is allowed to depend on the sequence of external inputs so far
02400 received by the system. Note that in this definition of "can" we are
02500 not requiring that "p" have any way of knowing what the external
02600 inputs were. An alternative definition requires the outputs to
02700 depend on the inputs of "p". This is equivalent to saying that "p"
02800 can achieve a goal provided the goal would be achieved for arbitrary
02900 inputs by some automaton put in place of "p". With either of these
03000 definitions "can" becomes a function of the place of the subautomaton
03100 in the system rather than of the subautomaton itself. We do not know
03200 which of these treatments is preferable, and so we shall call the
03300 first concept "cana" and the second "canb".
03400 The idea that what a person can do depends on his position
03500 rather than on his characteristics is somewhat counter-intuitive.
03600 This impression can be mitigated as follows: Imagine the person to be
03700 made up of several subautomata; the output of the outer subautomaton
03800 is the motion of the joints. If we break the connection to the world
03900 at that point we can answer questions like,`Can he fit through a
04000 given hole?` We shall get some counter-intuitive answers, however,
04100 such as that he can run at top speed for an hour or can jump over a
04200 building, since these are sequences of motions of his joints that
04300 would achieve these results.
04400 The next step, however, is to consider a subautomaton that
04500 receives the nerve impulses from the spinal cord and transmits them
04600 to the muscles. If we break at the input to this automaton, we shall
04700 no longer say that he can jump over a building or run long at top
04800 speed since the limitations of the muscles will be taken into
04900 account. We shall, however, say that he can ride a unicycle since
05000 appropriate nerve signals would achieve this result.
00100 The notion of "can" corresponding to the intuitive notion in
00200 the largest number of cases might be obtained by hopythesizing an
00300 `organ of will,` which makes decisions to do things and transmits
00400 these decisions to the main part of the brain that tries to carry
00500 them out and contains all the knowledge of particular facts. If we
00600 make the break at this point we shall be able to say that so-and-so
00700 cannot dial the President`s secret and private telephone number
00800 because he does not know it, even though if the question were asked
00900 could he dial that particular number, the answer would be yes.
01000 However, even this break would not give the statement, `I cannot go
01100 without saying goodbye, because this would hurt the child`s
01200 feelings`.
01300 On the basis of these examples, one might try to postulate a
01400 sequence of narrower and narrower notions of "can" terminating in a
01500 notion according to which a person can do only what he actually does.
01600 This notion would then be superfluous. Actually, one should not look
01700 for a single best notion of "can;" each of the above-mentioned
01800 notions is useful and is actually used in some circumstances.
01900 Sometimes, more than one notion is used in a single sentence, when
02000 two different levels of constraint are mentioned.
02100 Besides its use in explicating the notion of "can," the
02200 automaton representation of the world is very suited for defining
02300 notions of causality. For, we may say that subautomaton "p" caused
02400 the condition "π" in state "s", if changing the output of "p" would
02500 prevent "π." In fact the whole idea of a system of interacting
02600 automata is just a formalization of the commonsense notion of
02700 causality.
02800 Moreover, the automaton representation can be used to
02900 explicate certain counterfactual conditional sentences. For example,
03000 we have the sentence, `If I had struck this match yesterday at this
03100 time it would have lit.` In a suitable automaton representation, we
03200 have a certain state of the system yesterday at that time, and we
03300 imagine a break made where the nerves lead from my head or perhaps at
03400 the output of my `decision box`, and the appropriate signals to
03500 strike the match having been made. Then it is a definite and
03600 decidable question about the system "S(p)", whether the match lights
03700 or not, depending on whether it is wet, etc. This interpretation of
03800 this kind of counterfactual sentence seems to be what is needed for
03900 RP to learn from its mistakes, by accepting or generating sentences
04000 of the form, `had I done thus-and-so I would have been successful, so
04100 I should alter my procedures in some way that would have produced the
04200 correct action in that case`.
04300 In the foregoing we have taken the representation of the
04400 situation as a system of interacting subautomata for granted.
04500 However, a given overall situation might be represented as a system
04600 of interacting subautomata in a number of ways, and different
04700 representations might yield different results about what a given
04800 subautomaton can achieve, what would have happened if some
04900 subautomaton had acted differently, or what caused what. Indeed, in
05000 a different representation, the same or corresponding subautomata
05100 might not be identifiable. Therefore, these notions depend on the
05200 representation chosen.
00100 For example, suppose a pair of Martians observe the situation
00200 in a room. One Martian analyses it as a collection of interacting
00300 people as we do, but the second Martian groups all the heads together
00400 into one subautomaton and all the bodies into another. (A creature
00500 from momentum space would regard the Fourier components of the
00600 distribution of matter as the separate interacting subautomata.) How
00700 is the first Martian to convince the second that his representation
00800 is to be preferred? Roughly speaking, he would argue that the
00900 interaction between the heads and bodies of the same person is closer
01000 than the interaction between the different heads, and so more of an
01100 analysis has been achieved from `the primordial muddle` with the
01200 conventional representation. He will be especially convincing when
01300 he points out that when the meeting is over the heads will stop
01400 interacting with each other, but will continue to interact with their
01500 respective bodies.
01600 We can express this kind of argument formally in terms of
01700 automata as follows: Suppose we have an autonomous automaton "A",
01800 that is an automaton without inputs, and let it have "k" states.
01900 Further, let "m" and "n" be two integers such that "m,n≥k". Now
02000 label "k" points of an "m-by-n" array with The states of "A". This
02100 can be done in "(mn)!" ways. For each of these ways we have a
02200 " (k) "
02300 representation of the automaton "A" as a system of an "m"-state
02400 automaton "B" interacting with an "n"-state automaton "C". Namely,
02500 corresponding to each row of the array we have a state of "B" and to
02600 each column a state of "C". The signals are in 1-1 correspondence
02700 with the states themselves; thus each subautomaton has just as many
02800 values of its output as it has states. Now it may happen that two of
02900 these signals are equivalent in their effect on the other
03000 subautomaton, and we use this equivalence relation to form
03100 equivalence classes of signals. We may then regard the equivalence
03200 classes as the signals themselves. Suppose then that there are now
03300 "r" signals from "B" to "C" and "s" signals from "C" to "B". We ask
03400 how small "r" and "s" can be taken in general compared to "m" and
03500 "n". The answer may be obtained by counting the number of
03600 inequivalent automata with "k" states and comparing it with the
03700 number of systems of two automata with "m" and "n" states
03800 respectively and "r" and "s" signals going in the respective
03900 directions. The result is not worth working out in detail, but tells
04000 us that only a few of the "k" state automata admit such a
04100 decomposition with "r" and "s" small compared to "m" and "n".
04200 Therefore, if an automaton happens to admit such a decomposition it
04300 is very unusual for it to admit a second such decomposition that is
04400 not equivalent to the first with respect to some renaming of states.
04500 Applying this argument to the real world, we may say that it is
04600 overwhelmingly probable that our customary decomposition of the world
04700 automaton into separate people and things has a unique, objective and
04800 usually preferred status. Therefore, the notions of "can," of
04900 causality, and of counterfactual associated with this decomposition
05000 also have a preferred status.
00100 In our opinion, this explains some of the difficulty
00200 philosophers have had in analysing counterfactuals and causality. For
00300 example, the sentence, `If I had struck this match yesterday, it
00400 would have lit` is meaningful only in terms of a rather complicated
00500 model of the world, which, however, has an objective preferred
00600 status. However, the preferred status of this model depends on its
00700 correspondence with a large number of facts. For this reason, it is
00800 probably not fruitful to treat an individual counterfactual
00900 conditional sentence in isolation.
01000 It is also possible to treat notions of belief and knowledge
01100 in terms of the automaton representation. We have not worked this
01200 out very far, and the ideas presented here should be regarded as
01300 tentative. We would like to be able to give conditions under which
01400 we may say that a subautomaton "p" believes a certain proposition.
01500 We shall not try to do this directly but only relative to a predicate
01600 "B(p)(s,w)". Here "s" is the state of the automaton "p" and "w" is
01700 a proposition; "B(p)(s,w)" is true if "p" is to be regarded as
01800 believing "w" when in state "s" and is false otherwise. With respect
01900 to such a predicate "B" we may ask the following questions:
02000 1. Are "p`s" beliefs consistent? Are they correct?
02100 2. Does "p" reason? That is, do new beliefs arise that are
02200 logical consequences of previous beliefs?
02300 3. Does "p" observe? That is, do true propositions about
02400 automata connected to "p" cause "p" to believe them?
02500 4. Does "p" behave rationally? That is, when "p" believes a
02600 sentence asserting that it should do something does "p"
02700 do it?
02800 5. Does "p" communicate in language "L"? That is, regarding
02900 the content of a certain input or output signal line as
03000 in a text in language "L", does this line transmit
03100 beliefs to or from "p"?
03200 6. Is "p" self-conscious? That is, does it have a fair
03300 variety of correct beliefs about its own beliefs and the
03400 processes that change them?
03500 It is only with respect to the predicate "B(p)" that all these
03600 questions can be asked. However, if questions 1 thru 4 are answered
03700 affirmatively for some predicate "B(p)", this is certainly
03800 remarkable, and we would feel fully entitled to consider "B(p)" a
03900 reasonable notion of belief.
04000 In one important respect the situation with regard to belief
04100 or knowledge is the same as it was for counterfactual conditional
04200 statements: no way is provided to assign a meaning to a single
04300 statement of belief or knowledge, since for any single statement a
04400 suitable "B(p)" can easily be constructed. Individual statements
04500 about belief or knowledge are made on the basis of a larger system
04600 which must be validated as a whole.
00100 2. FORMALISM
00200
00300 In part 1 we showed how the concepts of ability and belief could be
00400 given formal definition in the metaphysically adequate automaton
00500 model and indicated the correspondence between these formal concepts
00600 and the corresponding commonsense concepts. We emphasized, however,
00700 that practical systems require epistemologically adequate systems in
00800 which those facts which are actually ascertainable can be expressed.
00900 In this part we begin the construction of an
01000 epistemologically adequate system. Instead of giving formal
01100 definitions, however, we shall introduce the formal notions by
01200 informal natural-language descriptions and give examples of their use
01300 to describe situations and the possibilities for action they present.
01400 The formalism presented is intended to supersede that of McCarthy
01500 (1963).
01600
01700 Situations
01800
01900 A situation "s" is the complete state of the universe at an instant
02000 of time. We denote by "Sit" the set of all situations. Since the
02100 universe is too large for complete description, we shall never
02200 completely describe a situation; we shall only give facts about
02300 situations. These facts will be used to deduce further facts about
02400 that situation, about future situations and about situations that
02500 persons can bring about from that situation.
02600 This requires that we consider not only situations that
02700 actually occur, but also hypothetical situations such as the
02800 situation that would arise if Mr. Smith sold his car to a certain
02900 person who has offered $250 for it. Since he is not going to sell
03000 the car for that price, the hypothetical situation is not completely
03100 defined; for example, it is not determined what Smith`s mental state
03200 would be and therefore it is also undetermined how quickly he would
03300 return to his office, etc. Nevertheless, the representation of
03400 reality is adequate to determine some facts about this situation,
03500 enough at least to make him decide not to sell the car.
03600 We shall further assume that the laws of motion determine,
03700 given a situation, all future situations.*
03800 In order to give partial information about situations we
03900 introduce the notion of fluent.
04000
04100
04200
04300 *This assumption is difficult to reconcile with quantum mechanics,
04400 and relativity tells us that any assignment of simultaneity to events
04500 in different places is arbitrary. However, we are proceeding on the
04600 basis that modern physics is irrelevant to common sense in deciding
04700 what to do, and in particular is irrelevant to solving the `free will
04800 problem`.
00100 Fluents
00200
00300 A "fluent" is a function whose domain is the space "Sit" of
00400 situations. If the range of the function is ("true, false"), then
00500 it is called a "propositional fluent." If its range is "Sit", then it
00600 is called a "situational fluent."
00700 Fluents are often the values of functions. Thus "raining"
00800 ("x") is a fluent such that "raining" ("x")("s") is true if and only
00900 if it is raining at the place "x" in the situation "s". We can also
01000 write this assertion as "raining"("x,s") making use of the well-known
01100 equivalence between a function of two variables and a function of the
01200 first variable whose value is a function of the second variable.
01300 Suppose we wish to assert about a situation "s" that person
01400 "p" is in place "x" and that it is raining in place "x". We may
01500 write this in several ways each of which has its uses:
01600
01700 1. "at(p,x)(s) ∧ raining (x)(s)." This corresponds to the
01800 definition given.
01900 2. "at(p,x,s) ∧ raining (x,s)." This is more conventional
02000 mathematically and a bit shorter.
02100 3. "[at(p,x) ∧ raining (x)](s)." Here we are introducing a
02200 convention that operators applied to fluents give fluents
02300 whose values are computed by applying the logical
02400 operators to the values of the operand fluents, that is,
02500 if "f" and "g" are fluents then
02600
02700 (f op g)(s)=f(s) op g(s)
02800
02900 4. "[λs`. at(p,x,s`) ∧ raining (x,s`)](s)." Here we have
03000 formed the composite fluent by λ-abstraction.
03100
03200 Here are some examples of fluents and expressions involving them:
03300
03400 1. "time(s)". This is the time associated with the
03500 situation "s". It is essential to consider time as
03600 dependent on the situation as we shall sometimes wish to
03700 consider several different situations having the same
03800 time value, for example, the results of alternative
03900 courses of actions.
04000 2. "in(x,y,s)". This asserts that "x" is in the location
04100 "y" in situation "s". The fluent "in" may be taken as
04200 satisfying a kind of transitive law, namely:
04300
04400 ∀x . ∀y . ∀z . ∀s in(x,y,s) ∧ in(y,z,s) ⊃ in(x,z,s)
04500
04600 We can also write this law
04700
04800 ∀x . ∀y . ∀z . ∀ . in(x,y) ∧ in(y,z) ⊃ in(x,z)
04900
00100 where we have adopted the convention that a quantifier
00200 without a variable is applied to an implicit situation
00300 variable which is the (suppressed) argument of a
00400 propositional fluent that follows. Suppressing situation
00500 arguments in this way corresponds to the natural language
00600 convention of writing sentences like, `John was at home`
00700 or `John is at home` leaving understood the situations to
00800 which these assertions apply.
00900 3. "has(Monkey,Bananas,s)". Here we introduce the
01000 convention that capitalized words denote proper names,
01100 for example, `Monkey` is the name of a particular
01200 individual. That the individual is a monkey is not
01300 asserted, so that the expression "monkey(Monkey)" may
01400 have to appear among the premisses of an argument.
01500 Needless to say, the reader has a right to feel that he
01600 has been given a hint that the individual Monkey will
01700 turn out to be a monkey. The above expression is to be
01800 taken as asserting that in the situation "s" the
01900 individual "Monkey" has the object "Bananas". We shall,
02000 in the examples below, sometimes omit premisses such as
02100 "monkey(Monkey), but in a complete system they would have
02200 to appear.
02300
02400
02500 Causality
02600
02700 We shall make assertions of causality by means of a fluent "F(π)"
02800 where "π" is itself a propositional fluent. "F(π,s)" asserts that
02900 the situation "s" will be followed (after an unspecified time) by a
03000 situation that satisfies the fluent "π".
03100 We may use "F" to assert that if a person is out in the rain
03200 he will get wet, by writing:
03300
03400 ∀x . ∀p . ∀s . raining(x,s) ∧ at(p,x,s) ∧ outside(p,s)
03500 ⊃ F(λs` .wet(p,s`),s)
03600
03700 Suppressing explicit mention of situations gives:
03800
03900 ∀x . ∀p . ∀ raining(x) ∧ at(p,x) ∧ outside(p) ⊃ F(wet(p)).
04000
04100 In this case suppressing situations simplifies the statement.
04200 "F" can also be used to express physical laws. Consider the
04300 law of falling bodies which is often written
04400
04500 h=h0+v0 . (t-t0)-0.5g. (t-t0)↑2
04600
04700 together with some prose identifying the variables. Since we need a
04800 formal system for machine reasoning we cannot have any prose.
04900 Therefore, we write:
00100
00200 ∀b . ∀t . ∀s . falling(b,s) ∧ t≥0 ∧ height(b,s)
00300 +velocity(b,s) . t-0.5gt↑2>0
00400 ⊃
00500
00600 F(λs` . time(s`)=time(s)+t ∧ falling(b,s`) ∧ height(b,s`)=
00700 height(b,s)+velocity(b,s) . t-0.5gt↑2,s)
00800 There has to be a convention (or declarations) so that it is
00900 determined that "height(b), velocity(b) and time" are fluents,
01000 whereas "t, v, t1" and "h" denote ordinary real numbers.
01100 "F(π,s)" as introduced here corresponds to A.N. Prior`s
01200 (1957, 1968) expression "Fπ".
01300 The use of situation variables is analogous to the use of
01400 time-instants in the calculi of world-states which Prior (1968) calls
01500 "U-T" calculi. Prior provides many interesting correspondences
01600 between his "U-T" calculi and various axiomatizations of the modal
01700 tense-logics (that is, using this "F"-operator: see part 4).
01800 However, the situation calculus is richer than any of the
01900 tense-logics Prior considers.
02000 Besides "F" he introduces three other operators which we also
02100 find useful; we thus have:
02200
02300 1. "F(π,s)." For some situation "s`" in the future of
02400 "s,π(s`)" holds.
02500 2. "G(π,s)." For all situations "s`" in the future of
02600 "s,π(s`)" holds.
02700 3. "P(π,s)." For some situations "s`" in the past of
02800 "s,π(s`)" holds.
02900 4. "H(π,s}." For all situations "s`" in the past of
03000 "s,π(s`)" holds.
03100
03200 It seems also useful to define a situational fluent "next(π)" as the
03300 next situation "s`" in the future of "s" for which "π(s`)" holds. If
03400 there is no such situation, that is, if¬"F(π,s)", then "next(π,s)" is
03500 considered undefined. For example, we may translate the sentence `By
03600 the time John gets home, Henry will be home too` as
03700 "at(Henry,home(Henry)next(at(John, home(John)),s))." Also the phrase
03800 `when John gets home` translates into "time(next(at(John,home
03900 (John)),s))."
04000 Though next "(π,s)" will never actually be computed since
04100 situations are too rich to be specified completely, the values of
04200 fluents applied to next "(π,s)" will be computed.
04300
04400
04500 Actions
04600
04700 A fundamental role in our study of actions is played by the
04800 situational fluent
04900
05000 result(p,st,s)
00100 Here, "p" is a person, "st" is an action or more generally a
00200 strategy, and "s" is a situation. The value of "result(p,st,s)" is
00300 the situation that results when "p" carries out "st", starting in the
00400 situation "s". If the action or strategy does not terminate,
00500 "result(p,st,s)" is considered undefined.
00600
00700 With the aid of "result" we can express certain laws of
00800 ability. For example:
00900
01000 has(p,k,s) ∧ fits(k,sf) ∧ at(p,sf,s) ⊃ open(sf,result(p,opens
01100 (sf,k),s))
01200
01300 This formula is to be regarded as an axiom schema asserting that if
01400 in a situation "s" a person "p" has a key "k" that fits the safe
01500 "sf", then in the situation resulting from his performing the action
01600 "opens(sf,k)", that is, opening the safe "sf" with the key "k", the
01700 safe is open. The assertion "fits(k,sf)" carries the information
01800 that "k" is a key and "sf" a safe. Later we shall be concerned with
01900 combination safes that require "p" to "know" the combination.
02000
02100
02200 Strategies
02300
02400 Actions can be combined into strategies. The simplest combination is
02500 a finite sequence of actions. We shall combine actions as though
02600 they were ALGOL statements, that is, procedure calls. Thus, the
02700 sequence of actions, (`move the box under the bananas`, `climb onto
02800 the box`, and `reach for the bananas`) may be written:
02900
03000 begin "move(Box,Under-Bananas); climb(Box); reach-for
03100 (Bananas)" end;
03200
03300 A strategy in general will be an ALGOL-like compound statement
03400 containing actions written in the form of procedure calling
03500 assignment statements, and conditional go to`s. We shall not include
03600 any declarations in the program since they can be included in the
03700 much larger collection of declarative sentences that determine the
03800 effect of the strategy.
03900 Consider for example the strategy that consists of walking 17
04000 blocks south, turning right and then walking till you come to
04100 Chestnut Street. This strategy may be written as follows:
04200
04300 begin
04400 face(South);
04500 n:=0;
04600 b: if n=17 then go to a;
04700 walk-a-block,n:=n+1;
04800 go to b;
04900 a: turn-right;
05000 c: walk-a-block;
05100 if name-on-street-sign≠`Chestnut Street` then go to c
05200 end;
00100 In the above program the external actions are represented by
00200 procedure calls. Variables to which values are assigned have a purely
00300 internal significance (we may even call it mental significance) and
00400 so do the statement labels and the go to statements.
00500 For the purpose of applying the mathematical theory of
00600 computation we shall write the program differently: namely, each
00700 occurrence of an action "α" is to be replaced by an assignment
00800 statement "s:result(p,α,s)." Thus the above program becomes
00900 begin
01000 s:=result(p,face(South),s);
01100 n:=0;
01200 b: if n=17 then go to a;
01300 s:=result(p,walk-a-block,s);
01400 n:=n+1;
01500 go to b;
01600 a: s:=result(p,turn-right,s);
01700 c: s:=result(p,walk-a-block,s);
01800 if name-on-street-sign(s)≠`Chestnut Street` then go to c.
01900 end;
02000
02100 Suppose we wish to show that by carrying out this strategy John can
02200 go home provided he is initially at his office. Then according to
02300 the methods of Zohar Manna (1968a, 1968b), we may derive from this
02400 program together with the initial condition "at(John,office
02500 (John),s0)" and the final condition "at(John,home(John),s)," a
02600 sentence "W" of first-order logic. Proving "W" will show that the
02700 procedure terminates in a finite number of steps and that when it
02800 terminates "s" will satisfy "at(John, home(John),s)."
02900 According to Manna`s theory we must prove the following
03000 collection of sentences inconsistent for arbitrary interpretations of
03100 the predicates "q1 " and "q2" and the particular interpretations of
03200 the other functions and predicates in the program:
03300
03400 at(John,office(John)s0),
03500 q1(O,result(John,face(South),s0)),
03600 ∀n . ∀s . q1(n,s) ⊃ if n=17
03700 then q2(result(John,walk-a-block,result
03800 (John,turn-right,s)))
03900 else q1(n+1,result(John,walk-a-block,s)),
04000 ∀s . q2(s) ⊃ if name-on-street-sign(s)≠`Chestnut Street`
04100 then q2(result(John,walk-a-block,s))
04200 else ¬at(John,home(John),s)
04300
04400 Therefore the formula that has to be proved may be written
04500
00100 ∃s0{at(John,office(John),s0) ∧ q1(O,result(John,face
00200 (South),s0))}
00300 ⊃
00400 ∃n . ∃s . {q1(n,s) ∧ if n=17
00500 then ∧ q2(result(John,walk-a-block,
00600 result
00700 (John,turn-right,s)))
00800 else ¬ q1(n+1,result(John,walk-a-
00900 block,s))}
01000 ∨
01100 ∃s . {q2(s) ∧ if name-on-street-sign(s)≠`Chestnut Street`
01200 then ¬ q2(result(John,walk-a-block,s))
01300 else at(John,home(John),s)}
01400
01500 In order to prove this sentence we would have to use the following
01600 kinds of facts expressed as sentences or sentence schemas of
01700 first-order logic:
01800 1. Facts of geography. The initial street stretches at
01900 least 17 blocks to the south, and intersects a street
02000 which in turn intersects Chestnut Street a number of
02100 blocks to the right; the location of John`s home and
02200 office.
02300 2. The fact that the fluent name-on-street-sign will have
02400 the value `Chestnut Stree` at that point.
02500 3. Facts giving the effects of action "α" expressed as
02600 predicates about "result(p,α,s)" deducible from sentences
02700 about "s".
02800 4. An axiom schema of induction that allows us to deduce
02900 that the loop of walking 17 blocks will terminate.
03000 5. A fact that says that Chestnut Street is a finite number
03100 of blocks to the right after going 17 blocks south. This
03200 fact has nothing to do with the possibility of walking.
03300 It may also have to be expressed as a sentence schema or
03400 even as a sentence of second-order logic.
03500
03600 When we consider making a computer carry out the strategy, we must
03700 distinguish the variable "s" from the other variables in the second
03800 form of the program. The other variables are stored in the memory of
03900 the computer and the assignments may be executed in the normal way.
04000 The variable "s" represents the state of the world and the computer
04100 makes an assignment to it by performing an action. Likewise the
04200 fluent name-on-street-sign requires an action, of observation.
04300
04400
04500 Knowledge and ability
04600
04700
04800 In order to discuss the role of knowledge in one`s ability to achieve
04900 goals let us return to the example of the safe. There we had
05000 1. has(p,k,s) ∧ fits(k,sf) ∧ at(p,sf,s) ⊃ open(sf,result(p,
05100 opens(sf,k),s)),
00100 which expressed sufficient conditions for the ability of a person to
00200 open a safe with a key. Now suppose we have a combination safe with
00300 a combination "c". Then we may write:
00400
00500 2. fits2(c,sf) ∧ at(p,sf,s) ⊃ open(sf,result(p,opens2
00600 (sf,c),s)).
00700
00800 where we have used the predicate "fits2" and the action "opens2" to
00900 express the distinction between a key fitting a safe and a
01000 combination fitting it, and also the distinction between the acts of
01100 opening a safe with a key and a combination. In particular,
01200 "opens2(sf,c)" is the act of manipulating the safe in accordance with
01300 the combination "c". We have left out a sentence of the form
01400 "has2(p,c,s)" for two reasons. In the first place, it is
01500 unnecessary: if you manipulate a safe in accordance with its
01600 combination it will open; there is no need to have anything. In the
01700 second place it is not clear what "has2(p,c,s)" means. Suppose, for
01800 example, that the combination of a particular safe "sf" is the number
01900 34125, then "fits"(34125, sf)" makes sense and so does the act
02000 "opens2(sf,34125)." (We assume that "open(sf,result
02100 (p,opens2(sf,34111),s)) would not be true.) But what could
02200 "has(p,34125,s) mean? Thus, a direct parallel between the rules for
02300 opening a safe with a key and opening it with a combination seems
02400 impossible.
02500 Nevertheless, we need some way of expressing the fact that
02600 one has to know the combination of a safe in order to open it.
02700 First we introduce the function "combination(sf)" and rewrite 2 as
02800
02900 3. at(p,sf,s) ∧ csafe(sf) ⊃ open(sf,result(p,opens2
03000 sf,combination(sf),s)))
03100
03200 where "csafe(sf)" asserts that "sf" is a combination safe and
03300 "combination (sf)" denotes the combination of "sf". (We could not
03400 write "(sf)" in the other case unless we wished to restrict ourselves
03500 to the case of safes with only one key.)
03600 Next we introduce the notion of a feasible strategy for a
03700 person. The idea is that a strategy that would achieve a certain goal
03800 might not be feasible for a person because he lacks certain knowledge
03900 or abilities.
04000 Our first approach is to regard the action
04100 "opens2d(sf,combination (sf))" as infeasible because "p" might not
04200 know the combination. Therefore, we introduce a new function
04300 "idea-of-combination(p,sf,s)" which stands for person "p`s" idea of
04400 the combination of "sf" in situation "s". The action
04500 "opens2(sf,idea-of-combination(p,sf,s))" is regarded as feasible for
04600 "p", since "p" is assumed to know his idea of the combination if this
04700 is defined. However, we leave sentence 3 as it is so we cannot yet
04800 prove "open(sf, result(p,opens2(sf,idea-of-combination(p,sf,s)),s))."
04900 The assertion that "p" knows the combination of "sf" can now be
05000 expressed as
05100 5. idea-of-combination(p,sf,s)=combination(sf)
00100 and with this, the possibility of opening the safe can be proved.
00200 Another example of this approach is given by the following
00300 formalization of getting into conversation with someone by looking up
00400 his number in the telephone book and then dialing it.
00500 The strategy for "p" in the first form is
00600
00700 begin
00800 lookup(q,Phone-book);
00900 dial(idea-of-phone-number(sq,p))
01000 end;
01100
01200 or in the second form
01300
01400 begin
01500 s:=result(p,lookup(q,Phone-book),s0);
01600 s:=result(p,dial(idea-of-phone-number(q,p,s)),s)
01700 end;
01800
01900 The premisses to write down appear to be
02000
02100 1. has(p,Phone-book,s0)
02200 2. listed(q,Phone-book,s0)
02300 3. ∀s . ∀p . ∀q . has(p,Phone-book,s) ∧ listed(q,
02400 Phone-book,s) ⊃ phone-number(q)=idea-of-phone-number
02500 p,q,result(p,lookup(q,Phone-book),s))
02600 4. ∀s . ∀p . ∀q . ∀x . at(q,home(q),s) ∧ has(p,x,s)
02700 ∧ telephone(x) ⊃ in-conversation(p,q,result(p,dial
02800 (phone-number(q)),s))
02900 5. at(q,home(q),s0)
03000 6. telephone(Telephone)
03100 7. has(p,Telephone,s0)
03200
03300 Unfortunately, these premisses are not sufficient to allow one to
03400 conclude that
03500
03600 in-conversation(p,q,result(p,begin lookup(q,Phone-book); dial
03700 (idea-of-phone-number(q,p))end;,s0)).
03800
03900 The trouble is that one cannot show that the fluents "at(q,home(q))"
04000 and "has(p,Telephone)" still apply to the situation "result(p,lookup
04100 (q, Phone-book),s0)." To make it come out right we shall revise the
04200 third hypothesis to read:
04300
04400 ∀s . ∀p . ∀q . ∀x . ∀y . at(q,y,s) ∧ has(p,x,s) ∧ has(p,Phone-
04500 book,s) ∧ listed(q,Phone-book) ⊃ [λr.at(q,y,r) ∧ has(p,x,r) ∧
04600 phone-number(q)=idea-of-phone-number(p,q,r)](result(p,lookup
04700 (q,Phone-book),s)).
04800
04900 This works, but the additional hypotheses about what remains
05000 unchanged when "p" looks up a telephone number are quite "ad hoc." We
05100 shall treat this problem in a later section.
00100 The present approach has a major technical advantage for
00200 which, however, we pay a high price. The advantage is that we
00300 preserve the ability to replace any expression by an equal one in any
00400 expression of our language. Thus if "phone-number(John)=3217580",
00500 any true statement of our language that contains 3217580 or
00600 "phone-number(John)" will remain true if we replace one by the other.
00700 This desirable property is termed referential transparency.
00800 The price we pay for referential transparency is that we have
00900 to introduce "idea-of-phone-number(p,q,s)" as a separate "ad hoc"
01000 entity and cannot use the more natural "idea-of(p,phone-number(q),s)"
01100 where "idea-of(p,con,s)" is some kind of operator applicable to the
01200 concept "con". Namely, the sentence"idea-of(p,phone-number
01300 (q),s)=phone-number(q)" would be supposed to express that "p" knows
01400 "q`s" phone-number, but "idea-of(p,3217580,s)=3217580" expresses only
01500 that "p" understands that number. Yet with transparency and the
01600 fact that "phone-number(q)=3217580" we could derive the former
01700 statement from the latter.
01800 A further consequence of our approach is that feasibility of
01900 a strategy is a referentially opaque concept since a strategy
02000 containing "idea-of-phone-number(p,q,s)" is regarded as feasible
02100 while one containing "phone-number(q)" is not, even though these
02200 quantities may be equal in a particular case. Even so, our language
02300 is still referentially transparent since feasibility is a concept of
02400 the metalanguage.
02500 A classical poser for the reader who wants to solve these
02600 difficulties to ponder is, `George IV wondered whether the author of
02700 the Waverly novels was Walter Scott` and `Walter Scott is the author
02800 of the Waverly novels`, from which we do not wish to deduce, `George
02900 IV wondered whether Walter Scott was Walter Scott`. This example and
03000 others are discussed in the first chapter of Church`s "Introduction
03100 to Mathematical Logic" (1956).
03200 In the long run it seems that we shall have to use a
03300 formalism with referential opacity and formulate precisely the
03400 necessary restrictions on replacement of equals by equals; the
03500 program must be able to reason about the feasibility of its
03600 strategies, and users of natural language handle referential opacity
03700 without disaster. In part 4 we give a brief account of the partly
03800 successful approach to problems of referential opacity in modal logic.
03900
04000
04100
04200 3. REMARKS AND OPEN PROBLEMS
04300
04400 The formalism presented in part 2 is, we think, an advance on
04500 previous attempts, but it is far from epistemological adequacy. In
04600 the following sections we discuss a number of problems that it
04700 raises. For some of them we have proposals that might lead to
04800 solutions.
00100 The approximate character of "result(p,st,s)".
00200
00300 Using the situational fluent "result(p,st,s)" in formulating the
00400 conditions under which strategies have given effects has two
00500 advantages over the "can(p,π,s)" of part 1. It permits more compact
00600 and transparent sentences, and it lends itself to the application of
00700 the mathematical theory of computation to prove that certain
00800 strategies achieve certain goals.
00900 However, we must recognize that it is only an approximation
01000 to say that an action, other than that which will actually occur,
01100 leads to a definite situation. Thus if someone is asked, `How would
01200 you feel tonight if you challenged him to a duel tomorrow morning and
01300 he accepted?` he might well reply, `I can`t imagine the mental state
01400 in which I would do it; if the words inexplicably popped out of my
01500 mouth as though my voice were under someone else`s control that would
01600 be one thing; if you gave me a longlasting belligerence drug that
01700 would be another.`
01800 From this we see that "result(p,st,s)" should not be regarded
01900 as being defined in the world itself, but only in certain
02000 representations of the world; albeit in representations that may have
02100 a preferred character as discussed in part 1.
02200 We regard this as a blemish on the smoothness of
02300 interpretation of the formalism, which may also lead to difficulties
02400 in the formal development. Perhaps another device can be found which
02500 has the advantages of "result" without the disadvantages.
02600
02700 Possible meanings of `can` for a computer program
02800
02900 A computer program can readily be given much more powerful means of
03000 introspection than a person has, for we may make it inspect the whole
03100 of its memory including program and data to answer certain
03200 introspective questions, and it can even simulate (slowly) what it
03300 would do with given initial data. It is interesting to list various
03400 notions of "can(Program,π)" for a program
03500
03600 1. There is a sub-program "st" and room for it in memory
03700 which would achieve "π" if it were in memory, and control
03800 were transferred to "st". No assertion is made that
03900 "Program" knows "st" or even knows that "st" exists.
04000 2. "st" exists as above and that "st" will achieve "π"
04100 follows from information in memory according to a proof
04200 that "Program" is capable of checking.
04300 3. "Program`s" standard problem-solving procedure will find
04400 "st" if achieving "π" is ever accepted as a subgoal.
04500
04600 The frame problem
04700
04800 In the last section of part 2, in proving that one person could get
04900 into conversation with another, we were obliged to add the hypothesis
05000 that if a person has a telephone he still has it after looking up a
05100 number in the telephone book. If we had a number of actions to be
05200 performed in sequence we would have quite a number of conditions to
00100 write down that certain actions do not change the values of certain
00200 fluents. In fact with "n" actions and "m" fluents we might have to
00300 write down "mn" such conditions.
00400 We see two ways out of this difficulty. The first is to
00500 introduce the notion of frame, like the state vector in McCarthy
00600 (1962). A number of fluents are declared as attached to the frame
00700 and the effect of an action is described by telling which fluents are
00800 changed, all others being presumed unchanged.
00900 This can be formalized by making use of yet more ALGOL
01000 notation, perhaps in a somewhat generalized form. Consider a
01100 strategy in which "p" performs the action of going from "x" to "y".
01200 In the first form of writing strategies we have "go(x,y)" as a
01300 program step. In the second form we have "s:=result(p,go(x,y),s)."
01400 Now we may write
01500
01600 location(p):=tryfor(y,x)
01700
01800 and the fact that other variables are unchanged by this action
01900 follows from the general properties of assignment statements. Among
02000 the conditions for successful execution of the program will be
02100 sentences that enable us to show that when this statement is
02200 executed, "tryfor(y,x)=y." If we were willing to consider that "p"
02300 could go anywhere we could write the assignment statement simply as
02400
02500 location(p):=y
02600
02700 The point of using "tryfor" here is that a program using this simpler
02800 assignment is, on the face of it, not possible to execute, since "p"
02900 may be unable to go to "y". We may cover this case in the more
03000 complex assignment by agreeing that when "p" is barred from
03100 "y,tryfor(y,x)=x."
03200 In general, restrictions on what could appear on the right
03300 side of an assignment to a component of the situation would be
03400 included in the conditions for the feasibility of the strategy.
03500 Since components of the situation that change independently in some
03600 circumstances are dependent in others, it may be worthwhile to make
03700 use of the block structure of ALGOL. We shall not explore this
03800 approach further in this paper.
03900 Another approach to the frame problem may follow from the
04000 methods of the next section; and in part 4 we mention a third
04100 approach which may be useful, although we have not investigated it at
04200 all fully.
04300
04400
04500 Formal literatures
04600
04700
04800 In this section we introduce the notion of formal literature which is
04900 to be contrasted with the well-known notion of formal language. We
05000 shall mention some possible applications of this concept in
05100 constructing an epistemologically adequate system.
00100 A formal literature is like a formal language with a history:
00200 we imagine that up to a certain time a certain sequence of sentences
00300 have been said. The literature then determines what sentences may be
00400 said next. The formal definition is as follows.
00500 Let "A" be a set of potential sentences, for example, the set
00600 of all finite strings in some alphabet. Let "Seq(A)" be the set of
00700 finite sequences of elements of "A" and let "L:Seq(A)→{true,false}"
00800 be such that if "sεSeq(A)" and "L(s)", that is "L(s)=true", and "s1"
00900 is an initial segment of "s" then "L(s1)." The pair "(A,L)" is termed
01000 a "literature". The interpretation is that "a(n)" may be said after
01100 "a1,....,a(n-1)," provided "L((a1,...,a(n)))". We shall also write
01200 "sεL" and refer to "s" as a string of the literature "L".
01300 From a literature "L" and a string "sεL" we introduce the
01400 derived literature "L(s)." Namely, "seq ε L(s)" if and only if "s*seq
01500 ε L," where "s*sq" denotes the concatenation of "s" and "seq".
01600 We shall say that the language "L" is universal for the class
01700 "LL" of literatures if for every literature "M ε LL" there is a
01800 string "s(M) ε L" such that "M=L(s(M));" that is, "seq ε M" if and
01900 only if "s(M)*seq ε L."
02000 We shall call a literature computable if its strings form a
02100 recursively enumerable set. It is easy to see that there is a
02200 computable literature "U(C)" that is universal with respect to the
02300 set "C" of computable literatures. Namely, let "e" be a computable
02400 literature and let "c" be the representation of the Godel number of
02500 the recursively enumerable set of "e" as a string of elements of "A".
02600 Then, we say "c*seq ε U(C)" if and only if "seq ε e".
02700 It may be more convenient to describe natural languages as
02800 formal literatures than as formal languages: if we allow the
02900 definition of new terms and require that new terms be used in
03000 accordance with their definitions, then we have restrictions on
03100 sentences that depend on what sentences have previously been uttered.
03200 In a programming language, the restriction that an identifier not be
03300 used until it has been declared, and then only consistently with the
03400 declaration, is of this form.
03500 Any natural language may be regarded as universal with
03600 respect to the set of natural languages in the approximate sense that
03700 we might define French in terms of English and then say `From now on
03800 we shall speak only French`.
03900 All the above is purely syntactic. The applications we
04000 envisage to artificial intelligence come from a certain kind of
04100 interpreted literature. We are not able to describe precisely the
04200 class of literatures that may prove useful, only to sketch a class of
04300 examples.
04400 Suppose we have an interpreted language such as first-order
04500 logic perhaps including some modal operators. We introduce three
04600 additional operators: "consistent(u), normally(u)," and
04700 "probably(u)." We start with a list of sentences as hypotheses. A
04800 new sentence may be added to a string "s" of sentences according to
04900 the following rules:
05000
00100 1. Any consequence of sentences of "s" may be added.
00200 2. If a sentence "u" is consistent with "s", then
00300 "consistent(u)" may be added. Of course, this is a
00400 non-computable rule. It may be weakened to say that
00500 "consistent(u)" may be added provided "u" can be shown to
00600 be consistent with "s" by some particular proof
00700 procedure.
00800 3. "normally(u), consistent(u) infers probably(u)."
00900 4. "u infers probably(u)" is a possible deduction.
01000 5. If "u1, u2,...,u(n) infers u" is a possible deduction
01100 then "probably(u1),...,probably(u(n)) infers probably(u)"
01200 is also a possible deduction.
01300 The intended application to our formalism is as follows:
01400 In part 2 we considered the example of one person telephoning
01500 another, and in this example we assumed that if "p" looks up "q`s"
01600 phone-number in the book, he will know it, and if he dials the number
01700 he will come into conversation with "q". It is not hard to think of
01800 possible exceptions to these statements such as:
01900 1. The page with "q`s" number may be torn out.
02000 2. "p" may be blind.
02100 3. Someone may have deliberately inked out "q`s" number.
02200 4. The telephone company may have made the entry
02300 incorrectly.
02400 5. "q" may have got the telephone only recently.
02500 6. The phone system may be out of order.
02600 7. "q" may be incapacitated suddenly.
02700
02800 For each of these possibilities it is possible to add a term
02900 excluding the difficulty in question to the condition on the result
03000 of performing the action. But we can think of as many additional
03100 difficulties as we wish, so it is impractical to exclude each
03200 difficulty separately.
03300 We hope to get out of this difficulty by writing such
03400 sentences as
03500
03600 ∀p . ∀q . ∀s . at(q,home(q),s) ⊃ normally(in-conversation(p,q,
03700 result(p,dials(phone-number(q)),s)))
03800
03900 We would then be able to deduce
04000
04100 probably(in-conversation(p,q,result(p,dials(phone-number(q)),
04200 s0)))
04300
04400 provided there were no statements like
04500
04600 kaput(Phone-system,s0)
04700
04800 and
04900
05000 ∀s . kaput(Phone-system,s) ⊃ ¬ in-conversation(p,q,result(p,
05100 dials(phone-number(q)),s))
05200 present in the system.
00100 Many of the problems that give rise to the introduction of
00200 frames might be handled in a similar way.
00300 The operators "normally, consistent" and "probably" are all
00400 modal and referentially opaque. We envisage systems in which
00500 "probably(π)" and "probably(¬π)" and therefore "probably(false)" will
00600 arise. Such an event should give rise to a search for a
00700 contradiction.
00800 We hereby warn the reader, if it is not already clear to him,
00900 that these ideas are very tentative and may prove useless, especially
01000 in their present form. However, the problem they are intended to
01100 deal with, namely the impossibility of naming every conceivable thing
01200 that may go wrong, is an important one for artificial intelligence,
01300 and some formalism has to be developed to deal with it.
01400
01500 Probabilities
01600
01700 On numerous occasions it has been suggested that the formalism take
01800 uncertainty into account by attaching probabilities to its sentences.
01900 We agree that the formalism will eventually have to allow statements
02000 about the probabilities of events, but attaching probabilities to all
02100 statements has the following objections:
02200 1. It is not clear how to attach probabilities to statements
02300 containing quantifiers in a way that corresponds to the
02400 amount of conviction people have.
02500 2. The information necessary to assign numerical
02600 probabilities is not ordinarily available. Therefore, a
02700 formalism that required numerical probabilities would be
02800 epistemologically inadequate.
02900 Besides describing strategies by ALGOL-like programs we may also want
03000 to describe the laws of change of the situation by such programs. In
03100 doing so we must take into account the fact that many processes are
03200 going on simultaneously and that the single-activity-at-a-time
03300 ALGOL-like programs will have to be replaced by programs in which
03400 processes take place in parallel, in order to get an
03500 epistemologically adequate description. This suggests examining the
03600 so-called simulation languages; but a quick survey indicates that
03700 they are rather restricted in the kinds of processes they allow to
03800 take place in parallel and in the types of interaction allowed.
03900 Moreover, at present there is no developed formalism that allows
04000 proofs of the correctness of parallel programs.
04100
04200
04300 4. DISCUSSION OF LITERATURE
04400
04500 The plan for achieving a generally intelligent program outlined in
04600 this paper will clearly be difficult to carry out. Therefore, it is
04700 natural to ask if some simpler scheme will work, and we shall devote
04800 this section to criticising some simpler schemes that have been
04900 proposed.
00100 1. L. Fogel (1966) proposes to evolve intelligent automata
00200 by altering their state transition diagrams so that they perform
00300 better on tasks of greater and greater complexity. The experiments
00400 described by Fogel involve machines with less than 10 states being
00500 evolved to predict the next symbol of a quite simple sequence. We do
00600 not think this approach has much chance of achieving interesting
00700 results because it seems limited to automata with small numbers of
00800 states, say less than 100, whereas computer programs regarded as
00900 automata have 2↑10↑5 to 2↑10↑7 states. This is a reflection of the
01000 fact that, while the representation of behaviours by finite automata
01100 is metaphysically adequate--in principle every behaviour of which a
01200 human or machine is capable can be so represented--this
01300 representation is not epistemologically adequate; that is, conditions
01400 we might wish to impose on a behaviour, or what is learned from an
01500 experience, are not readily expresible as changes in the state
01600 diagram of an automaton.
01700 2. A number of investigators (Galanter 1956, Pivar and
01800 Finkelstein 1964) have taken the view that intelligence may be
01900 regarded as the ability to predict the future of a sequence from
02000 observation of its past. Presumably, the idea is that the experience
02100 of a person can be regarded as a sequence of discrete events and that
02200 intelligent people can predict the future. Artificial intelligence is
02300 then studied by writing programs to predict sequences formed
02400 according to some simple class of laws (sometimes probabilistic
02500 laws). Again the model is metaphysically adequate but
02600 epistemologically inadequate.
02700 In other words, what we know about the world is divided into
02800 knowledge about many aspects of it, taken separately and with rather
02900 weak interaction. A machine that worked with the undifferentiated
03000 encoding of experience into a sequence would first have to solve the
03100 encoding, a task more difficult than any the sequence extrapolators
03200 are prepared to undertake. Moreover, our knowledge is not usable to
03300 predict exact sequences of experience. Imagine a person who is
03400 correctly predicting the course of a football game he is watching; he
03500 is not predicting each visual sensation (the play of light and
03600 shadow, the exact movements of the players and the crowd). Instead
03700 his prediction is on the level of: team A is getting tired; they
03800 should start to fumble or have their passes intercepted.
03900 3. Friedberg (1958,1959) has experimented with representing
04000 behaviour by a computer program and evolving a program by random
04100 mutations to perform a task. The epistemological inadequacy of the
04200 representation is expressed by the fact that desired changes in
04300 behaviour are often not representable by small changes in the machine
04400 language form of the program. In particular, the effect on a
04500 reasoning program of learning a new fact is not so representable.
04600 4. Newell and Simon worked for a number of years with a
04700 program called the General Problem Solver (Newell "et. al." 1959,
04800 Newell and Simon 1961). This program represents problems as the
04900 task of transforming one symbolic expression into another using a
05000 fixed set of transformation rules. They succeeded in putting a fair
05100 variety of problems into this form, but for a number of problems the
05200 representation was awkward enough so that GPS could only do small
00100 examples. The task of improving GPS was studied as a GPS task, but
00200 we believe it was finally abandoned. The name, General Problem
00300 Solver, suggests that its authors at one time believed that most
00400 problems could be put in its terms, but their more recent
00500 publications have indicated other points of view.
00600 It is interesting to compare the point of view of the present
00700 paper with that expressed in Newell and Ernst (1965) from which we
00800 quote the second paragraph:
00900
01000 We may consider a problem solver to be a process that takes a
01100 problem as input and provides (when successful) the solution
01200 as output. The problem consists of the problem statement, or
01300 what is immediately given, and auxiliary information, which
01400 is potentially relevant to the problem but available only as
01500 the result of processing. The problem solver has available
01600 certain methods for attempting to solve the problem. For the
01700 problem solver to be able to work on a problem it must first
01800 transform the problem statement from its external form into
01900 the internal representation. Thus (roughly), the class of
02000 problems the problem solver can convert into its internal
02100 representation determines how broad or general it is, and its
02200 success in obtaining solutions to problems in internal form
02300 determines its power. Whether or not universal, such a
02400 decomposition fits well the structure of present problem
02500 solving programs.
02600
02700 In a very approximate way their division of the problem solver into
02800 the input program that converts problems into internal representation
02900 and the problem solver proper corresponds to our division into the
03000 epistemological and heuristic pats of the artificial intelligence
03100 problem. The difference is that we are more concerned with the
03200 suitability of the internal representation itself.
03300 Newell (1965) poses the problem of how to get what we call
03400 heuristically adequate representations of problems, and Simon (1966)
03500 discusses the concept of `can` in a way that should be compared with
03600 the present approach.
03700 Modal logic
03800 It is difficult to give a concise definition of modal logic. It was
03900 originally invented by Lewis (1918) in an attempt to avoid the
04000 `paradoxes` of implication (a false proposition implies any
04100 proposition). The idea was to distinguish two sorts of truth:
04200 "necessary" truth and mere "contingent" truth. A contingently true
04300 proposition is one which, though true, could be false. This is
04400 formalized by introducing the modal operator "N" (read `necessarily`)
04500 which forms propositions from propositions. Then "p`s" being a
04600 necessary truth is expressed by "Np`s" being true. More recently,
04700 modal logic has become a much-used tool for analysing the logic of
04800 such various propositional operators as belief, knowledge and tense.
04900 There are very many possible axiomatizations of the logic of
05000 "N" none of which seem more intuitively plausible than many others. A
05100 full account of the main classical systems is given by Feys (1965),
05200 who also includes an excellent bibliography. We shall give here an
00100 axiomatization of a fairly simple modal logic, the system "M" of
00200 Feys-Von Wright. One adds to any full axiomatization of
00300 propositional calculus the following:
00400
00500 Ax. 1: Np⊃p
00600 Ax.2:N(p⊃p)⊃(Np⊃Nq)
00700 Rule 1: from "p" and "p⊃q", infer "q"
00800 Rule 2: from "p", infer "Np".
00900 (This axiomatization is due to Godel).
01000
01100 There is also a dual modal operator "P", defined as "¬N¬". Its
01200 intuitive meaning is `possibly`: "Pp" is true when "p" is at least
01300 possible, although "p" may be in fact false (or true). The reader
01400 will be able to see the intuitive correspondence between "¬Pp-p" is
01500 impossible, and "N¬p-" that is, "p", is necessarily false.
01600 "M" is a fairly weak modal logic. One can strengthen it by
01700 adding axioms, for example, adding "Ax.3: Np⊃NNp" yields the system
01800 called "S4"; adding "Ax.4:Pp⊃NPp" yields "S5"; and other additions
01900 are possible. However, one can also weaken all the systems in
02000 various ways, for instance by changing "Ax.1" to "Ax.1`:Np⊃Pp". One
02100 easily sees that "Ax.1" implies "Ax.1`", but the converse is not
02200 true. The systems obtained in this way are known as the "deontic"
02300 versions of the systems. These modifications will be useful later
02400 when we come to consider tense-logics as modal logics.
02500 One should note that the truth or falsity of "Np" is not
02600 decided by "p`s" being true. Thus "N" is not a truth-functional
02700 operator (unlike the usual logical connectives, for instance) and so
02800 there is no direct way of using truth-tables to analyse propositions
02900 containing modal operators. In fact the decision problem for modal
03000 propositional calculi has been quite nontrivial. It is just this
03100 property which makes modal calculi so useful, as belief, tense, etc.,
03200 when interpreted as propositional operators, are all
03300 nontruthfunctional.
03400
03500 The proliferation of modal propositional calculi, with no
03600 clear means of comparison, we shall call the "first problem" of modal
03700 logic. Other difficulties arise when we consider modal predicate
03800 calculi, that is, when we attempt to introduce quantifiers. This was
03900 first done by Barcan-Marcus (1946).
04000 Unfortunately, all the early attempts at modal predicate
04100 calculi had unintuitive theorems ("see" for instance Kripke 1963a),
04200 and, moreover, all of them met with difficulties connected with the
04300 failure of Leibniz` law of identity, which we shall try to outline.
04400 Leibniz` law is
04500
04600 L:∀x . ∀y . x=y ⊃ (F(x)≡F(y))
04700
04800 where "F" is any open sentence. Now this law fails in modal
04900 contexts. For instance, consider this instance of "L":
05000
05100 L1: ∀x . ∀y . x=y ⊃ (N(x=x)≡N(x=y))
00100 By rule 2 of "M" (which is present in almost all modal logics), since
00200 %"x=x"% is a theorem, so is "N(%x=x%)." Thus "L1" yields
00300
00400 L2: ∀x . ∀y . x=y ⊃ N(x=y)
00500
00600 But, the argument goes, this is counterintuitive. For instance the
00700 morning star is in fact the same individual as the evening star (the
00800 planet Venus). However, they are not "necessarily" equal: one can
00900 easily imagine that they might be distinct. This famous example is
01000 known as the `morning star paradox`.
01100 This and related difficulties compel one to abandon Leibniz`
01200 law in modal predicate calculi, or else to modify the laws of
01300 quantification (so that it is impossible to obtain the undesirable
01400 instances of universal sentences such as "L2"). This solves the
01500 purely formal problem, but leads to severe difficulties in
01600 interpreting these calculi, as Quine has urged in several papers (cf.
01700 Quine 1964).
01800 The difficulty is this. A sentence "F(a)" is usually thought
01900 of as ascribing some property to a certain individual "a". Now
02000 consider the morning star; clearly, the morning star is necessarily
02100 equal to the morning star. However, the evening star is not
02200 necessarily equal to the morning star. Thus, this one
02300 individual--the planet Venus--both has and does not have the property
02400 of being necessarily equal to the morning star. Even if we abandon
02500 proper names the difficulty does not disappear: for how are we to
02600 interpret a statement like "∃x . ∃y(x=y ∧ F(x) ∧ ¬ F(y))"?
02700 Barcan-Marcus has urged an unconventional reading of the
02800 quantifiers to avoid this problem. The discussion between her and
02900 Quine in Barcan-Marcus (1963) is very illuminating. However, this
03000 raises some difficulties--see Belnap and Dunn (1968)--and the recent
03100 semantic theory of modal logic provides a more satisfactory method of
03200 interpreting modal sentences.
03300 This theory was developed by several authors (Hintikka 1963,
03400 1967a; Kanger 1957; Kripke 1963a, 1963b, 1965), but chiefly by
03500 Kripke. We shall try to give an outline of this theory, but if the
03600 reader finds it inadequate he should consult Kripke (1963a).
03700 The idea is that modal calculi describe several "possible
03800 worlds" at once, instead of just one. Statements are not assigned a
03900 single truth-value, but rather a spectum of truth-values, one in each
04000 possible world. Now, a statement is necessary when it is true in
04100 "all" possible worlds--more or less. Actually, in order to get
04200 different modal logics (and even then not all of them) one has to be
04300 a bit more subtle, and have a binary relation on the set of possible
04400 worlds--the alternativeness relation. Then a statement is necessary
04500 in a world when it is true in all alternatives to that world. Now it
04600 turns out that many common axioms of modal propositional logics
04700 correspond directly to conditions of alternativeness. Thus for
04800 instance in the system "M" above, "Ax.1" corresponds to the
04900 reflexiveness of the alternativeness relation; "Ax.3(Np⊃NNp)"
05000 corresponds to its transitivity. If we make the alternativeness
05100 relation into an equivalence relation, then this is just like not
05200 having one at all; and it corresponds to the axiom: "Pp⊃NPp".
00100 This semantic theory already provides an answer to the first
00200 problem of modal logic: a rational method is available for
00300 classifying the multitude of propositional modal logics. More
00400 importantly, it also provides an intelligible interpretation for
00500 modal predicate calculi. One has to imagine each possible world as
00600 having a set of individuals and an assignment of individuals to names
00700 of the language. Then each statement takes on its truthvalue in a
00800 world "s" according to the particular set of individuals and
00900 assignment associated with "s". Thus, a possible world is an
01000 interpretation of the calculus, in the usual sense.
01100 Now, the failure of Leibniz` law is no longer puzzling, for
01200 in one world the morning star--for instance--may be equal to (the
01300 same individual as) the evening star, but in another the two may be
01400 distinct.
01500 There are still difficulties, both formal--the quantification
01600 rules have to be modified to avoid unintuitive theorems (see Kripke,
01700 1963a, for the details)--and interpretative: it is not obvious what
01800 it means to have the "same" individual existing in "different"
01900 worlds.
02000 It is possible to gain the expressive power of modal logic
02100 without using modal operators by constructing an ordinary
02200 truth-functional logic which describes the multiple-world semantics
02300 of modal logic directly. To do this we give every predicate an extra
02400 argument (the world-variable; or in our terminology the
02500 situation-variable) and instead of writing `"NF`", we write
02600
02700 ∀t . A(s,t) ⊃ F(t),
02800
02900 where "A" is the alternativeness relation between situations. Of
03000 course we must provide appropriate axioms for "A".
03100 The resulting theory will be expressed in the notation of the
03200 situation calculus; the proposition "F" has become a propositional
03300 fluent "λs.F(s)", and the `possible worlds` of the modal semantics
03400 are precisely the situations. Notice, however, that the theory we get
03500 is weaker than what would have been obtained by adding modal
03600 operators directly to the situation calculus, for
03700 we can give no translation of assertions such as "Nπ(s)", where "s"
03800 is a situation, which this enriched situation calculus would contain.
03900 It is possible, in this way, to reconstruct within the
04000 situation calculus subtheories corresponding to the tense-logics of
04100 Prior and to the knowledge logics of Hintikka, as we shall explain
04200 below. However, there is a qualification here: so far we have only
04300 explained how to translate the propositional modal logics into the
04400 situation calculus. In order to translate quantified modal logic,
04500 with its difficulties of referential opacity, we must complicate the
04600 situation calculus to a degree which makes it rather clumsy. There
04700 is a special predicate on individuals and situation--"exists(i,s)"--
04800 which is regarded as true when "i" names an individual existing in
04900 the situation "s". This is necessary because situations may contain
05000 different individuals. Then quantified assertions of the modal
05100 logic are translated according to the following scheme:
00100 ∀x . F(x) → ∀x . exists(x,s) ⊃ F(x,s)
00200
00300 where "s" is the introduced situation variable.
00400 We shall not go into the details of this extra translation in
00500 the examples below, but shall be content to define the translations
00600 of the propositional tense and knowledge logics into the situation
00700 calculus.
00800
00900
01000 Logic of knowledge
01100
01200 The logic of knowledge was first investigated as a modal logic by
01300 Hintikka in his book "Knowledge and belief" (1962). We shall only
01400 describe the knowledge calculus. He introduces the modal operator
01500 "Ka" (read `a knows that`), and its dual "Pa", defined as "¬Ka¬".
01600 The semantics is obtained by the analogous reading of "Ka" as: `it is
01700 true in all possible worlds compatible with "a`s" knowledge that`.
01800 The propositional logic of "Ka" (similar to "N") turns out to be
01900 "S4", that is "M+Ax.3"; but there are some complexities over
02000 quantification. (The last chapter of the book contains another
02100 excellent account of the overall problem of quantification in modal
02200 contexts.) This analysis of knowledge has been criticized in various
02300 ways (Chisholm 1963, Follesdal 1967) and Hintikka has replied in
02400 several important papers (1967b, 1967c , 1969). The last paper
02500 contains a review of the different senses of `know` and the extent to
02600 which they have been adequately formalized. It appears that two
02700 senses have resisted capture. First, the idea of `knowing how`,
02800 which appears related to our `can`; and secondly, the concept of
02900 knowing a person (place, etc.) when this means `being acquainted
03000 with` as opposed to simply knowing "who" a person "is".
03100 In order to translate the (propositional) knowledge calculus
03200 into `situation` language, we introduce a three-place predicate into
03300 the situation calculus termed `shrug`. "Shrug(p,s1,s2)", where "p"
03400 is a person and "s1" and "s2" are situations, is true when, if "p" is
03500 in fact in situation "s2", then for all he knows he might be in
03600 situation "s1". That is to say, "s1" is an "epistemic alternative"
03700 to "s2", as far as the individual "p" is concerned--this is
03800 Hintikka`s term for his alternative worlds (he calls them modelsets).
03900
04000 Then we translate "K(p)q", where "q" is a proposition of
04100 Hintikka`s calculus, as "∀t . shrug(p,t,s) ⊃ q(t)", where "λs.q(s)"
04200 is the fluent which translates "q". Of course we have to supply
04300 axioms for "shrug", and in fact so far as the pure knowledge-calculus
04400 is concerned, the only two necessary are
04500
04600 K1: ∀s . ∀p . shrug(p,s,s)
04700
04800 and K2: ∀p . ∀s . ∀t .∀r . (shrug(p,t,s) ∧ shrug(p,r,t)) ⊃
04900 shrug(p,r,s)
05000
05100 that is, reflexivity and transitivity.
00100 Others of course may be needed when we add tenses and other
00200 machinery to the situation calculus, in order to relate knowledge to
00300 them.
00400
00500
00600 Tense logics
00700
00800 This is one of the largest and most active areas of philosophic
00900 logic. Prior`s book "Past, present and future" (1968) is an
01000 extremely thorough and lucid account of what has been done in the
01100 field. We have already mentioned the four propositional operators
01200 "F, G, P, H" which Prior discusses. He regards these as modal
01300 operators; then the alternativeness relation of the semantic theory
01400 is simply the time-ordering relation. Various axiomatizations are
01500 given, corresponding to deterministic and nondeterministic tenses,
01600 ending and nonending times, etc; and the problems of quantification
01700 turn up again here with renewed intensity. To attempt a summary of
01800 Prior`s book is a hopeless task, and we simply urge the reader to
01900 consult it. More recently several papers have appeared (see, for
02000 instance, Bull 1968) which illustrate the technical sophistication
02100 tense-logic has reached, in that full completeness proofs for various
02200 axiom systems are now available.
02300 As indicated above, the situation calculus contains a
02400 tense-logic (or rather several tense-logics), in that we can define
02500 Prior`s four operators in our system and by suitable axioms
02600 reconstruct various axiomatizations of these four operators (in
02700 particular, all the axioms in Bull (1968) can be translated into the
02800 situation calculus).
02900 Only one extra nonlogical predicate is necessary to do this:
03000 it is a binary predicate of situations called "cohistorical", and is
03100 intuitively meant to assert of its arguments that one is in the
03200 other`s future. This is necessary because we want to consider some
03300 pairs of situations as being not temporally related at all. We now
03400 define "F" (for instance) thus:
03500 F(π,s) ≡ ∃t . cohistorical(t,s) ∧ time(t)>time(s) ∧ π(t).
03600
03700 The other operators are defined analogously.
03800 Of course we have to supply axioms for `cohistorical` and
03900 time: this is not difficult. For instance, consider one of Bull`s
04000 axioms, say "Gp⊃GGp", which is better (for us) expressed in the form
04100 "FFp⊃Fp". Using the definition, this translates into:
04200
04300 (∃t . cohistorical(t,s) ∧ time(t) > time(s) ∧ ∃r .
04400 cohistorical(r,t)
04500
04600 ∧ time(r) > time(t) ∧ π(r)) ⊃ (∃r . cohistorical(r,s)
04700
04800 ∧time(r) > time(s) ∧ π(r))
04900
05000 which simplifies (using the transitivity of `>`) to
00100 ∀t . ∀r . (cohistorical(r,t) ∧ cohistorical(t,s)) ⊃
00200 cohistorical(r,s)
00300
00400 that is, the transitivity of `cohistorical`. This axiom is precisely
00500 analogous to the "S4" axiom "Np⊃NNp", which corresponded to
00600 transitivity of the alternativeness relation in the modal semantics.
00700 Bull`s other axioms translate into conditions on `cohistorical` and
00800 time in a similar way; we shall not bother here with the rather
00900 tedious details.
01000 Rather more interesting would be axioms relating `shrug` to
01100 `cohistorical` and time; unfortunately we have been unable to think
01200 of any intuitively plausible ones. Thus, if two situations are
01300 epistemic alternatives (that is, "shrug(p,s1,s2))" then they may or
01400 may not have the same time value (since we want to allow that "p" may
01500 not know what the time is), and they may or may not be cohistorical.
01600
01700
01800 Logics and theories of actions
01900
02000 The most fully developed theory in this area is von Wright`s action
02100 logic described in his book "Norm and Action" (1963). Von Wright
02200 builds his logic on a rather unusual tense-logic of his own. The
02300 basis is a binary modal connective "T", so that "pTq", where "p" and
02400 "q" are propositions, means "`p,thenq`". Thus the action, for
02500 instance, of opening the window is: "(the window is closed)T(the
02600 window is open)". The formal development of the calculus was taken a
02700 long way in the book cited above, but some problems of interpretation
02800 remained as Castaneda points out in his review (1965). In a more
02900 recent paper von Wright (1967) has altered and extended his formalism
03000 so as to answer these and other criticisms, and also has provided a
03100 sort of semantic theory based on the notion of a life-tree.
03200 We know of no other attempts at constructing a single theory
03300 of actions which have reached such a degree of development, but there
03400 are several discussions of difficulties and surveys which seem
03500 important. Rescher (1967) discusses several topics very neatly, and
03600 Davidson (1967) also makes some cogent points. Davidson`s main
03700 thesis is that, in order to translate statements involving actions
03800 into the predicate calculus, it appears necessary to allow actions as
03900 values of bound variables, that is (by Quine`s test) as real
04000 individuals. The situation calculus of course follows this advice in
04100 that we allow quantification over strategies, which have actions as a
04200 special case. Also important are Simon`s papers (1965, 1967) on
04300 command-logics. Simon`s main purpose is to show that a special logic
04400 of commands is unnecessary, ordinary logic serving as the only
04500 deductive machinery; but this need not detain us here. He makes
04600 several points, most notably perhaps that agents are most of the time
04700 not performing actions, and that in fact they only stir to action
04800 when forced to by some outside interference. He has the particularly
04900 interesting example of a serial processor operating in a
05000 parallel-demand environment, and the resulting need for interrupts.
05100 Action logics such as von Wright`s and ours do not distinguish
05200 between action and inaction, and we are not aware of any action-logic
00100 which has reached a stage of sophistication adequate to meet Simon`s
00200 implied criticism.
00300 There is a large body of purely philosophical writings on
00400 action, time, determinism, etc., most of which is irrelevant for
00500 present purposes. However, we mention two which have recently
00600 appeared and which seem interesting: a paper by Chisholm (1967) and
00700 another paper by Evans (1967), summarizing the recent discussion on
00800 the distinctions between states, performances and activities.
00900
01000
01100 Other topics
01200
01300 There are two other areas where some analysis of actions has been
01400 necessary: command-logics and logics and theories of obligation. For
01500 the former the best refevence is Rescher`s book (1966) which has an
01600 excellent bibliography. Note also Simon`s counterarguments to some of
01700 Rescher`s theses (Simon 1965, 1967). Simon proposes that no special
01800 logic of commands is necessary, commands being analysed in the form
01900 `bring it about that "p"!` for some proposition "p", or, more
02000 generally, in the form `bring it about that "P(x)" by changing "x"!`,
02100 where "x" is a "command" variable, that is, under the agent`s
02200 control. The translations between commands and statements take place
02300 only in the context of a `complete model`, which specifies
02400 environmental constraints and defines the command variables. Rescher
02500 argues that these schemas for commands are inadequate to handle the
02600 "conditional command" `when "p", do "q"`, which becomes `bring it
02700 about that "(p⊃q)"!: this, unlike the former, is satisfied by making
02800 "p" false.
02900 There are many papers on the logic of obligation and
03000 permission. Von Wright`s work is oriented in this direction;
03100 Castaneda has many papers on the subject and Anderson also has
03200 written extensively (his early influential report (1956) is
03300 especially worth reading). The review pages of the "Journal of
03400 Symbolic Logic" provide many other references. Until fairly recently
03500 these theories did not seem of very much relevance to logics of
03600 action, but in their new maturity they are beginning to be so.
03700
03800
03900 Counterfactuals
04000
04100
04200 There is, of course, a large literature on this ancient philosophical
04300 problem, almost none of which seems directly relevant to us.
04400 However, there is one recent theory, developed by Rescher (1964),
04500 which may be of use. Rescher`s book is so clearly written that we
04600 shall not attempt a description of his theory here. The reader
04700 should be aware of Sosa`s critical review (1967) which suggests some
04800 minor alterations.
04900 The importance of this theory for us is that it suggests an
05000 alternative approach to the difficulty which we have referred to as
05100 the frame problem. In outline, this is as follows. One assumes, as
05200 a rule of procedure (or perhaps as a rule of inference), that when
00100 actions are performed, "all" propositional fluents which applied to
00200 the previous situation also apply to the new situation. This will
00300 often yield an inconsistent set of statements about the new
00400 situation; Rescher`s theory provides a mechanism for restoring
00500 consistency in a rational way, and giving as a by-product those
00600 fluents which change in value as a result of performing the action.
00700 However, we have not investigated this in detail.
00800
00900
01000 The communication process
01100
01200 We have not considered the problems of formally describing the
01300 process of communication in this paper, but it seems clear that they
01400 will have to be tackled eventually. Philosophical logicians have
01500 been spontaneously active here. The major work is Harrah`s book
01600 (1963); Cresswell has written several papers on `the logic of
01700 interrogatives`, see for instance Cresswell (1965). Among other
01800 authors we may mention Aqvist (1965) and Belnap (1963); again the
01900 review pages of the "Journal of Symbolic Logic" will provide other
02000 references.
02100
02200
02300 Acknowledgements
02400
02500 The research reported here was supported in part by the Advanced
02600 Research Projects Agency of the Office of the Secretary of Defense
02700 (SD-183), and in part by the Science Research Council (B/SR/2299)
02800
00100 REFERENCES
00200
00300
00400
00500 Anderson, A.R. (1956) The formal analysis of normative systems.
00600 Reprinted in "The Logic of decision and action" (ed. Rescher,
00700 N.). Pittsburgh: University of Pittsburgh Press.
00800 Aqvist, L. (1965) " A new approach to the logical theory of
00900 interrogatives, part I." Uppsala: Uppsala Philosophical
01000 Association.
01100 Barcan-Marcus, R.C. (1946) A functional calculus of the first order
01200 based on strict implication. "Journal of Symbolic Logic", 11,
01300 1-16.
01400 Barcan-Marcus, R.C. (1963) Modalities and intensional languages.
01500 "Boston studies in the Philosophy of Science." (ed.
01600 Wartofsky, W.). Dordrecht, Holland.
01700 Belnap, N.D. (1963) "An analysis of questions." Santa Monica.
01800 Belnap, N.D. and Dunn, J.M. (1968) The substitution interpretation of
01900 the quantifiers. "Nous", 2, 177-85.
02000 Bull, R.A. (1968) An algebraic study of tense logics with linear
02100 time. "Journal of Symbolic Logic", 33, 27-39.
02200 Castaneda, H.N. (1965) The logic of change, action and norms.
02300 "Journal of Philosophy", 62, 333-4.
02400 Chisholm, R.M. (1963) The logic of knowing. "Journal of Philosophy",
02500 60, 773-95.
02600 Chisholm, R.M. (1967) He could have done otherwise. "Journal of
02700 Philosophy", 64, 409-17.
02800 Church, A. (1956) "Introduction to Mathematical Logic." Princeton:
02900 Princeton University Press.
03000 Cresswell, M.J. (1965) The logic of interrogatives. "Formal systems
03100 and recursive functions." (ed. Crossley, J.M. and Dummett,
03200 M.A.E.). Amsterdam: North-Holland.
03300 Davidson, D. (1967) The logical form of action sentences. "The logic
03400 of decision and action." (ed. Rescher, N.). Pittsburgh:
03500 University of Pittsburgh Press.
03600 Evans, C.O. (1967) States, activities and performances. "Australian
03700 Journal of Philosophy, 45, 293-308.
03800 Feys, R. (1965) "Modal Logics." (ed. Dopp, J.). Louvain: Coll. de
03900 Logique Math. serie B.
04000 Fogel, L.J., Owens, A.J. and Walsh, M.J. (1966) "Artificial
04100 Intelligence through simulated evolution." New York: John
04200 Wiley.
04300 Follesdal, D. (1967) Knowledge, identity and existence. "Theoria",
04400 33, 1-27.
04500 Friedberg, R.M. (1958) A learning machine, part I. "IBM J. Res.
04600 Dev.", 2, 2-13.
04700 Friedberg, R.M., Dunham, B., and North, J.H. (1959) A learning
04800 machine, part II. "IBM J. Res. Dev.", 3, 282-7.
04900 Galanter, E. and Gerstenhaber, M. (1956) On thought: the extrinsic
05000 theory. "Psychological Review", 63, 218-27.
00100 Green, C. (1969) Theorem-proving by resolution as a basis for
00200 question-answering systems. "Machine Intelligence 4," pp.
00300 183-205 (eds. Meltzer, B. and Michie, D.). Edinburgh:
00400 Edinburgh University Press.
00500 Harrah, D. (1963) " Communication: a logical model." Cambridge,
00600 Massachusetts: MIT Press.
00700 Hintikka, J. (1962) "Knowledge and belief: an introduction to the
00800 logic of two notions." New York: Cornell University Press.
00900 Hintikka, J. (1963) The modes of modality. "Acta Philosophica
01000 Fennica", 16, 65-82.
01100 Hintikka, J. (1967a) A program and a set of concepts for
01200 philosophical logic. "The Monist," 51, 69-72.
01300 Hintikka, J. (1967b) Existence and identity in epistemic contexts.
01400 "Theoria," 32, 138-47.
01500 Hintikka, J. (1967c) Individuals, possible worlds and epistemic
01600 logic. "Nous," 1, 33-62.
01700 Hintikka, J. (1969) Alternative constructions in terms of the basic
01800 epistemological attitudes. "Contemporary philosophy in
01900 Scandinavia" (ed. Olsen, R.E.) (to appear).
02000 Kanger, S. (1957) A note on quantification and modalities. "Theoria,"
02100 23, 133-4.
02200 Kripke, S. (1963a) Semantical considerations on modal logic. "Acta
02300 Philosophica Fennica," 16, 83-94.
02400 Kripke, S. (1963b) Semantical analysis of modal logic I. "Zeitschrift
02500 fur math. Logik und Grundlagen der Mathematik," 9, 67-96.
02600 Kripke, S. (1965) Semantical analysis of modal logic II. "The theory
02700 of models" (eds. Addison, Henkin and Tarski). Amsterdam:
02800 North-Holland.
02900 Lewis, C.I. (1918) "A survey of symbolic logic." Berkeley: University
03000 of California Press.
03100 Manna, Z. (1968a) "Termination of algorithms." Ph.D. Thesis,
03200 Carnegie-Mellon University.
03300 Manna, Z. (1968b) "Formalization of properties of programs" Stanford
03400 Artificial Intelligence Report: Project Memo AI-64.
03500 McCarthy, J. (1959) Programs with common sense. "Mechanization of
03600 thought processes," Vol. I. London: HMSO.
03700 McCarthy, J. (1962) Towards a mathematical science of computation.
03800 "Proc. IFIP Congress" 62. Amsterdam: North-Holland Press.
03900 McCarthy, J. (1963) "Situations, actions and causal laws." Stanford
04000 Artificial Intelligence Project: Memo 2.
04100 Minsky, M. (1961) Steps towards artificial intelligence. "Proceedings
04200 of the I.R.E.," 49, 8-30.
04300 Newell, A., Shaw, V.C. and Simon, H.A. (1959) Report on a general
04400 problem-solving program. "Proceedings ICIP." Paris:UNESCO
04500 House.
04600 Newell, A. and Simon, H.A. (1961) GPS - a program that simulates
04700 human problem-solving. "Proceedings of a conference in
04800 learning automata." Munich:Oldenbourgh.
04900 Newell, A. (1965) Limitations of the current stock of ideas about
05000 problem-solving. "Proceedings of a conference on Electronic
05100 Information Handling," pp. 195-208 (eds. Kent, A. and
05200 Taulbee, O.). New York: Spartan.
00100 Newell, A. & Ernst, C. (1965) The search for generality. "Proc. IFIP
00200 Congress 65".
00300 Pivar, M. & Finkelstein, M. (1964) "The Programming Language LISP:
00400 its operation and applications" (eds. Berkely, E.C. & Bobrow,
00500 D.G.). Cambridge, Massachusetts: MIT Press.
00600 Prior, A.N. (1957) "Time and modality." Oxford: Clarendon Press.
00700 Prior, A.N. (1968) "Past, present and future." Oxford: Clarendon
00800 Press.
00900 Quine, W.V.O. (1964) Reference and modality. "From a logical point of
01000 view." Cambridge, Massachusetts: Harvard University Press.
01100 Rescher, N. (1964) "Hypothetical reasoning." Amsterdam:
01200 North-Holland.
01300 Rescher, N. (1966) "The logic of commands." London: Routledge.
01400 Rescher, N. (1967) Aspects of action. "The logic of decision and
01500 action" (ed. Rescher, N.). Pittsburgh: University of
01600 Pittsburgh Press.
01700 Shannon, C. (1950) Programming a computer for playing chess.
01800 "Philosophical Magazine, 41.
01900 Simon, H.A. (1965) The logic of rational decision. "British Journal
02000 for the Philosophy of Science," 16, 169-86.
02100 Simon, H.A (1966) "On Reasoning about actions." Carnegie Institute of
02200 Technology: Complex Information Processing Paper 87.
02300 Simon, H.A. (1967) The logic of heuristic decision making. "The logic
02400 of decision and action "(ed. Rescher, N.). Pittsburgh:
02500 University of Pittsburgh Press.
02600 Sosa, E. (1967) Hypothetical reasoning. "Journal of Philosophy," 64,
02700 293-305.
02800 Turing, A.M. (1950) Computing machinery and intelligence. "Mind," 59,
02900 433-60.
03000 von Wright, C.H. (1963) "Norm and action: a logical enquiry." London:
03100 Routledge.
03200 von Wright, C.H. (1967) The Logic of Action - a sketch. "The logic of
03300 decision and action" (ed. Rescher, N.). Pittsburgh:University
03400 of Pittsburgh Press.
03500